[math-fun] Strong pseudoprimes [Jaeschke, Gilchrist, Feitsma]
Gerhard Jaeschke tabulated all 101 composites N<10^12 that pass the Miller pseudoprime tests with A=2, 3 and 5. Of these 101, Jaeschke found 95 had the form N=p*q with p,q odd primes with (q-1) = k*(p-1) for k in the set {2,3,4,5,6,7,13, 4/3, 5/2}. Thus, combining (i) the Miller tests with A=2,3,5 with (ii) trying integers very near sqrt(N/k) as possible divisors of N with (iii) a lookup table for the remaining 6 exceptions yields a prime test valid for N<10^12. Gerhard Jaeschke: On strong pseudoprimes to several bases, Maths. of Comput. 61,204 (1993) 915-926. http://cr.yp.to/bib/1993/jaeschke.pdf Jaeschke also claims that there are no strong pseudoprimes below 10^12, common to the four prime bases A=2, 13, 23, and 1662803. Further, if we examine the 6 exceptional N below 10^12, which are 151*751*28351 note 750/150=5, 28350/150=189=7*3*3*3 ** 397*4357*8317 note 4356/396=11, 8316/396=21=3*7 ** 331*2971*49171 note 2970/330=9, 49170/330=149 151*2551*192601 note 2550/150=17, 192600/150=1284=2*2*3*107 1171*10531*19891 note 10530/1170=9, 19890/1170=17 ** 1231*6151*11071 note 6150/1230=5, 11070/1230=9=3*3 ** we see that four out of these six N (those with **) would have been spotted if we had tried integers very near cbrt(N/m) as potential factors of N for the m with 45<=m<=945 got by multiplying {3,5,7,11,17} in various combinations with at most 4 prime factors (counting repeated factors repeatedly) in all and with at most one factor>7 allowed in the mix. http://oeis.org/A006945 also is relevant to this. --- Jeff Gilchrist has a web page on this: http://gilchrist.ca/jeff/factoring/pseudoprimes.html and he finds using Jan Feitsma's 2-pseudoprime database http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html that the $620 prize problem (of finding a composite N which is both Miller pseudoprime with A=2 and also Lucas pseudoprime according to the Baillie-PSW test) has no solution below 2^64. This particular Lucas test employs P=1 and Q=(1-D)/4 where D is the first member of {5, -7, 9, -11, 13, -15, ...} for which GCD(D,N)=1 and JacobiSymbol(D|N) = -1.
Just a curiosity, but two of the six exceptions below fit into the (q-1)=k(p-1) test, albeit with composite p. 151*751*28351 = 28351 * 113401 151*2551*192601 = 192601 * 385201 Rich -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Warren Smith Sent: Wednesday, January 18, 2012 4:12 PM To: math-fun@mailman.xmission.com Subject: [EXTERNAL] [math-fun] Strong pseudoprimes [Jaeschke, Gilchrist, Feitsma] Gerhard Jaeschke tabulated all 101 composites N<10^12 that pass the Miller pseudoprime tests with A=2, 3 and 5. Of these 101, Jaeschke found 95 had the form N=p*q with p,q odd primes with (q-1) = k*(p-1) for k in the set {2,3,4,5,6,7,13, 4/3, 5/2}. Thus, combining (i) the Miller tests with A=2,3,5 with (ii) trying integers very near sqrt(N/k) as possible divisors of N with (iii) a lookup table for the remaining 6 exceptions yields a prime test valid for N<10^12. Gerhard Jaeschke: On strong pseudoprimes to several bases, Maths. of Comput. 61,204 (1993) 915-926. http://cr.yp.to/bib/1993/jaeschke.pdf Jaeschke also claims that there are no strong pseudoprimes below 10^12, common to the four prime bases A=2, 13, 23, and 1662803. Further, if we examine the 6 exceptional N below 10^12, which are 151*751*28351 note 750/150=5, 28350/150=189=7*3*3*3 ** 397*4357*8317 note 4356/396=11, 8316/396=21=3*7 ** 331*2971*49171 note 2970/330=9, 49170/330=149 151*2551*192601 note 2550/150=17, 192600/150=1284=2*2*3*107 1171*10531*19891 note 10530/1170=9, 19890/1170=17 ** 1231*6151*11071 note 6150/1230=5, 11070/1230=9=3*3 ** we see that four out of these six N (those with **) would have been spotted if we had tried integers very near cbrt(N/m) as potential factors of N for the m with 45<=m<=945 got by multiplying {3,5,7,11,17} in various combinations with at most 4 prime factors (counting repeated factors repeatedly) in all and with at most one factor>7 allowed in the mix. http://oeis.org/A006945 also is relevant to this. --- Jeff Gilchrist has a web page on this: http://gilchrist.ca/jeff/factoring/pseudoprimes.html and he finds using Jan Feitsma's 2-pseudoprime database http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html that the $620 prize problem (of finding a composite N which is both Miller pseudoprime with A=2 and also Lucas pseudoprime according to the Baillie-PSW test) has no solution below 2^64. This particular Lucas test employs P=1 and Q=(1-D)/4 where D is the first member of {5, -7, 9, -11, 13, -15, ...} for which GCD(D,N)=1 and JacobiSymbol(D|N) = -1. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Schroeppel, Richard -
Warren Smith