mersenneforum.org Sale!! 1/2 Price Fermat Test
 Register FAQ Search Today's Posts Mark Forums Read

 2019-03-09, 21:59 #1 a1call     "Rashid Naimi" Oct 2015 Out of my Body 181810 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)^(q-1) == 1 is equivalent to : Mod(b,q)^((q-1)/2) == 1 || Mod(b,q)^((q-1)/2) == q-1 for all positive odd q.
2019-03-10, 01:46   #2
paulunderwood

Sep 2002
Database er0rr

7·467 Posts

Quote:
 Originally Posted by a1call Well it doesn't really cost 1/2 the core time but the exponent is 1/2 as large: Mod(b,q)^(q-1) == 1 is equivalent to : Mod(b,q)^((q-1)/2) == 1 || Mod(b,q)^((q-1)/2) == q-1 for all positive odd q.
Euler knew a better definition some 300 years ago

 2019-03-10, 01:59 #3 a1call     "Rashid Naimi" Oct 2015 Out of my Body 2·32·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)^((q-1)/(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 | q-1. the test's performance can be improved as: (Mod(b,q)^/((q-1)/(2^i)))^(2^j) for j
2019-03-10, 02:16   #4
paulunderwood

Sep 2002
Database er0rr

7·467 Posts

Quote:
 Originally Posted by a1call 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.
Pari/GP has the function kronecker() which covers jacobi. So you would write:

Code:
Mod(b,q)^((q-1)/2) == kronecker(b,q)
Note also that if the number is congruent to 1 mod 4 and the root is 1, you can take another square root and the answer should be +1 or -1. If it is 1 and the number is congruent to 1 mod 8 then you can take yet another square root and so on -- this "strong test" is the basis of the Miller-Rabin (M-R) test.

 2019-03-10, 02:35 #5 a1call     "Rashid Naimi" Oct 2015 Out of my Body 111000110102 Posts Thank you very much Paul for your great insights. Hopefully a Pari-GP code will make my gibberish more clear: Code:  \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ \\CQL-100-A - 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)==d-1, 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 ETA Don't know of any case where "lift(m^j)==1 " is applicable. Last fiddled with by a1call on 2019-03-10 at 02:40
 2019-03-10, 03:39 #6 danaj   "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. Miller-Rabin) 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post airsquirrels Hardware 8 2017-05-29 05:23 princeps Math 15 2012-04-02 21:49 Arkadiusz Math 6 2011-04-05 19:39 bearnol Miscellaneous Math 9 2005-11-16 13:19 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 08:30.

Sun Jul 5 08:30:20 UTC 2020 up 102 days, 6:03, 1 user, load averages: 1.03, 1.19, 1.17