mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-03-09, 21:59   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

17·107 Posts
Default 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.

a1call is offline   Reply With Quote
Old 2019-03-10, 01:46   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×409 Posts
Default

Quote:
Originally Posted by a1call View Post
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
paulunderwood is online now   Reply With Quote
Old 2019-03-10, 01:59   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

17·107 Posts
Default

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<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 2019-03-10 at 02:26
a1call is offline   Reply With Quote
Old 2019-03-10, 02:16   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·409 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
paulunderwood is online now   Reply With Quote
Old 2019-03-10, 02:35   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Out of my Body

17×107 Posts
Default

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
a1call is offline   Reply With Quote
Old 2019-03-10, 03:39   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90210 Posts
Default

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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
For sale allows here? airsquirrels Hardware 8 2017-05-29 05:23
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
The fastest primality test for Fermat numbers. Arkadiusz Math 6 2011-04-05 19:39
Fermat's Fuzzy Theorem - any good for new prime test? bearnol Miscellaneous Math 9 2005-11-16 13:19
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

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

Tue Jul 7 08:03:23 UTC 2020 up 104 days, 5:36, 1 user, load averages: 1.59, 1.28, 1.18

Powered by vBulletin® Version 3.8.11
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.