20190309, 21:59  #1 
"Rashid Naimi"
Oct 2015
Out of my Body
1818_{10} Posts 
Sale!! 1/2 Price Fermat Test
Well it doesn't really cost 1/2 the core time but the exponent is 1/2 as large:
Mod(b,q)^(q1) == 1 is equivalent to : Mod(b,q)^((q1)/2) == 1  Mod(b,q)^((q1)/2) == q1 for all positive odd q. 
20190310, 01:46  #2  
Sep 2002
Database er0rr
7·467 Posts 
Quote:


20190310, 01:59  #3 
"Rashid Naimi"
Oct 2015
Out of my Body
2·3^{2}·101 Posts 
Yes, that guy was quite something.
I think the only reason he is not considered the most intelligent person ever, is because most people do not understand what he says. Not so With the Einstein's and the Newton's. Incidentally thank you for the link but I can't figure anything out of that. ETA: OK, so I had to dig in all the way to "Legendre symbol" to figure it out. Thanks again for the reference. At the level of i=2, Mod(b,q)^((q1)/(2^i)) the test returns true for all primes and some pseudoprimes. For values of i>2 the test returns true for a subset of primes given 2^i  q1. the test's performance can be improved as: (Mod(b,q)^/((q1)/(2^i)))^(2^j) for j<i and the performance is better the closer j is to i. The point is for a select few primes the probabilistic test can be performed at the very low cost of modular exponentiation to a value as small as to prime q. I know it's sounds gibberish but that's the best I could describe it. Last fiddled with by a1call on 20190310 at 02:26 
20190310, 02:16  #4  
Sep 2002
Database er0rr
7·467 Posts 
Quote:
Code:
Mod(b,q)^((q1)/2) == kronecker(b,q) 

20190310, 02:35  #5 
"Rashid Naimi"
Oct 2015
Out of my Body
11100011010_{2} Posts 
Thank you very much Paul for your great insights.
Hopefully a PariGP code will make my gibberish more clear: Code:
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \\CQL100A  Low cost PRP test by Rashid Naimi q=2 theFlag=0 i=26 theCheckDepth = 13; while (!theFlag,{ q=nextprime(q+1); d=2^i*q+1; \\d=2^38*q+1; m= (Mod (2,d)^q); theRealFlag =0; for(j=1,theCheckDepth , if( lift(m^j)==1  lift(m^j)==d1, theRealFlag =1; print("**** Found a (Probable) Prime at Depth: ",j); print(theRealFlag ," > ",d); next(1); ); ); if ( theRealFlag , print (q); print ("**** 2^",i,"*",q,"+1"); print (d); print (#digits (d)," dd"); print ( isprime (d)); \\next (19); ); }) ## Code:
**** Found a (Probable) Prime at Depth: 4 1 > 282649554904416257 **** Found a (Probable) Prime at Depth: 8 1 > 282649554904416257 **** Found a (Probable) Prime at Depth: 12 1 > 282649554904416257 4211806579 **** 2^26*4211806579+1 282649554904416257 18 dd 1 Last fiddled with by a1call on 20190310 at 02:40 
20190310, 03:39  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
For the case of base 2, you can go even one step further. It is even more discriminating than the Fermat and Euler tests, though less than a full strong pseudoprime (i.e. MillerRabin) test. To my knowledge this was first noted by Colin Plumb in 1995. It is measurably faster than the other two tests over a variety of input, though nothing crazy (it reduces the exponent by either 2 or 4 and because of base 2 we don't need to calculate the Jacobi / Kronecker symbol).
See, e.g. bnlib 1.1 and the discussion in this Mersennseforum thread. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
For sale allows here?  airsquirrels  Hardware  8  20170529 05:23 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
The fastest primality test for Fermat numbers.  Arkadiusz  Math  6  20110405 19:39 
Fermat's Fuzzy Theorem  any good for new prime test?  bearnol  Miscellaneous Math  9  20051116 13:19 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 