mersenneforum.org Primality testing non-Mersennes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-24, 21:29 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25·32 Posts Primality testing non-Mersennes Hi, I've used P95 to identify a number of smallish PRPs. They are not of the form 2p-1. One in particular is $3^{19217} - 2$ which I believe has 9169 digits. I assume, in a world tackling the search for Megaprimes, that the fact this is not available on The Prime Database means that this is composite. However, I'd like to test this myself... Is it possible to do this with P95? To get a proof one way or another. Or is there some alternative software which can test a prime like this? Thanks, Luke
 2018-01-24, 21:44 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2018-01-24, 21:58   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by lukerichards Hi, I've used P95 to identify a number of smallish PRPs. They are not of the form 2p-1. One in particular is $3^{19217} - 2$ which I believe has 9169 digits. I assume, in a world tackling the search for Megaprimes, that the fact this is not available on The Prime Database means that this is composite. However, I'd like to test this myself... Is it possible to do this with P95? To get a proof one way or another. Or is there some alternative software which can test a prime like this? Thanks, Luke
You can even use your brain ( literally proved it in my head it doesn't have divisors below 19) modular tricks can be used.

2018-01-24, 22:04   #4
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

5×863 Posts

Quote:
 Originally Posted by lukerichards I assume, in a world tackling the search for Megaprimes, that the fact this is not available on The Prime Database means that this is composite.
Eh? Which database are you referring to?

If you find a number is PRP, it is very very very likely prime. Two different PRP tests convince most folks, but since exceptions exist a proof is required to call it prime. Assuming any PRP is not prime isn't a wise plan- you either find documentation it's an exception (PRP but not prime, I mean), or you should assume it's actually a prime.

2018-01-24, 22:21   #5
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

28810 Posts

Quote:
 Originally Posted by science_man_88 You can even use your brain ( literally proved it in my head it doesn't have divisors below 19) modular tricks can be used.
Eh?

2018-01-24, 22:25   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by lukerichards Eh?
An extention of Fermat's little theorem is what I used.

2018-01-24, 22:26   #7
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts

Quote:
 Originally Posted by VBCurtis Eh? Which database are you referring to? If you find a number is PRP, it is very very very likely prime. Two different PRP tests convince most folks, but since exceptions exist a proof is required to call it prime. Assuming any PRP is not prime isn't a wise plan- you either find documentation it's an exception (PRP but not prime, I mean), or you should assume it's actually a prime.
Thanks.

I was referring to Primes.utm.edu but I've since realised their database only searches for top5000 primes, not all primes.

2018-01-24, 22:27   #8
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts

Quote:
 Originally Posted by science_man_88 An extention of Fermat's little theorem is what I used.
To test that a 9000 digit number was prime in your head? Impressive. Could you elaborate?

2018-01-24, 22:30   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by lukerichards To test that a 9000 digit number was prime in your head? Impressive. Could you elaborate?
a^(k*(p-1)) is congruent to 1 mod p. I trial factored up to p = 19.

Last fiddled with by science_man_88 on 2018-01-24 at 23:02 Reason: Fixed major typo

 Similar Threads Thread Thread Starter Forum Replies Last Post 1260 Software 17 2015-08-28 01:35 CRGreathouse Computer Science & Computational Number Theory 18 2013-06-08 19:12 wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25 mdettweiler Conjectures 'R Us 18 2008-03-04 00:06 jasong Math 1 2007-11-06 21:46

All times are UTC. The time now is 07:25.

Wed Sep 23 07:25:08 UTC 2020 up 13 days, 4:36, 0 users, load averages: 2.53, 2.40, 2.14

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.