20180124, 21:29  #1 
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}×3^{2} Posts 
Primality testing nonMersennes
Hi,
I've used P95 to identify a number of smallish PRPs. They are not of the form 2^{p}1. One in particular is 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 
20180124, 21:44  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·2,399 Posts 
http://factordb.com/index.php?query=3%5E192172
It was proven prime in July 2015 by a member of this forum. He probably used the Primo software for it. It's not too difficult to establish the compositeness (or lack thereof) of such small numbers. Even using Python and a naivelysimple implementation of the Euler PRP test or MillerRabin test can quickly establish that it is a least a pseudoprime (or composite for other similar sized numbers) in a minute or two on a nowslow Sandy Bridge laptop. For all further efforts, I highly recommend using the FactorDB as your launching point. Last fiddled with by Dubslow on 20180124 at 21:48 
20180124, 21:58  #3  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:


20180124, 22:04  #4  
"Curtis"
Feb 2005
Riverside, CA
3^{2}×499 Posts 
Quote:
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. 

20180124, 22:21  #5 
"Luke Richards"
Jan 2018
Birmingham, UK
100100000_{2} Posts 

20180124, 22:25  #6 
"Forget I exist"
Jul 2009
Dumbassville
20261_{8} Posts 

20180124, 22:26  #7  
"Luke Richards"
Jan 2018
Birmingham, UK
2^{5}·3^{2} Posts 
Quote:
I was referring to Primes.utm.edu but I've since realised their database only searches for top5000 primes, not all primes. 

20180124, 22:27  #8 
"Luke Richards"
Jan 2018
Birmingham, UK
440_{8} Posts 

20180124, 22:30  #9 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
a^(k*(p1)) is congruent to 1 mod p. I trial factored up to p = 19.
Last fiddled with by science_man_88 on 20180124 at 23:02 Reason: Fixed major typo 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Testing an expression for primality  1260  Software  17  20150828 01:35 
Testing Mersenne cofactors for primality?  CRGreathouse  Computer Science & Computational Number Theory  18  20130608 19:12 
a new Deterministic primality testing  wsc812  Computer Science & Computational Number Theory  36  20130304 06:25 
Automated primality testing with LLRnet  mdettweiler  Conjectures 'R Us  18  20080304 00:06 
a new primality testing method  jasong  Math  1  20071106 21:46 