Dear Prof. Davenport,
I was just looking at your modifications of the primality test in axiom,
especially th two “maximal 2-part” test from Primality Testing Revisited.
After I while I found the following short explanation:
count2Order(k) counts the number of b such that
b^((n-1)/2) = -1 (mod n).
If n is prime, then b^((n-1)/2) is just the Legendre symbol
legendre(b, n), and -1 for exactly half of the b's. Of course, if n is
not prime, we might still get some -1, which explains why we should
first do some checks disregarding count2Order.
I could not see however why one tests count2Order(k) = 0, and does not
require count2Order(k) to exceed a proportion of the number of tests.
It is also unclear to my why you collect more information than, namely
the number of b^(q*2^j) congruent to -1 mod n for all j.
Did you have plans for a more accurate check? For your convenience, I
attach the source.
Besides that, I also noticed the failure prime?(149491*747451*34233211)
giving true. Zhenxiang Zhang, Two kinds of strong pseudoprimes up to
10^36 conjectures that this number is actually psi_11, i.e. the smallest
strong pseudoprime to all the first 11 prime bases. Maybe we need to
update the algorithm, it's just one more step :-)
(49) -> rabinProvesComposite(37, n, n-1, q, k)
(49) true
I hope you are doing well,
Martin Rubey
rabinProvesCompositeSmall(p,n,nm1,q,k) ==
-- probability n prime is > 3/4 for each iteration
-- for most n this probability is much greater than 3/4
t := powmod(p, q, n)
-- neither of these cases tells us anything
if not (one? t or t = nm1) then
for j in 1..k-1 repeat
oldt := t
t := mulmod(t, t, n)
one? t => return true
-- we have squared someting not -1 and got 1
t = nm1 =>
leave
not (t = nm1) => return true
false
rabinProvesComposite(p,n,nm1,q,k) ==
-- probability n prime is > 3/4 for each iteration
-- for most n this probability is much greater than 3/4
t := powmod(p, q, n)
-- neither of these cases tells us anything
if t=nm1 then count2Order(1):=count2Order(1)+1
if not (one? t or t = nm1) then
for j in 1..k-1 repeat
oldt := t
t := mulmod(t, t, n)
one? t => return true
-- we have squared someting not -1 and got 1
t = nm1 =>
rootsMinus1:=union(rootsMinus1,oldt)
count2Order(j+1):=count2Order(j+1)+1
leave
not (t = nm1) => return true
# rootsMinus1 > 2 => true -- Z/nZ can't be a field
false
prime? n ==
n < two => false
n < nextSmallPrime => member?(n, smallPrimes)
not one? gcd(n, productSmallPrimes) => false
n < nextSmallPrimeSquared => true
nm1 := n-1
q := (nm1) quo two
for k in 1.. while not odd? q repeat q := q quo two
-- q = (n-1) quo 2^k for largest possible k
n < JaeschkeLimit =>
rabinProvesCompositeSmall(2::I,n,nm1,q,k) => return false
rabinProvesCompositeSmall(3::I,n,nm1,q,k) => return false
n < PomeranceLimit =>
rabinProvesCompositeSmall(5::I,n,nm1,q,k) => return false
member?(n,PomeranceList) => return false
true
rabinProvesCompositeSmall(7::I,n,nm1,q,k) => return false
n < PinchLimit =>
rabinProvesCompositeSmall(10::I,n,nm1,q,k) => return false
member?(n,PinchList) => return false
true
rabinProvesCompositeSmall(5::I,n,nm1,q,k) => return false
rabinProvesCompositeSmall(11::I,n,nm1,q,k) => return false
n < PinchLimit2 =>
member?(n,PinchList2) => return false
true
rabinProvesCompositeSmall(13::I,n,nm1,q,k) => return false
rabinProvesCompositeSmall(17::I,n,nm1,q,k) => return false
true
rootsMinus1:= empty()
count2Order := new(k,0) -- vector of k zeroes
mn := minIndex smallPrimes
for i in mn+1..mn+10 repeat
rabinProvesComposite(smallPrimes i,n,nm1,q,k) => return false
import IntegerRoots(I)
q > 1 and perfectSquare?(3*n+1) => false
((n9:=n rem (9::I))=1 or n9 = -1) and perfectSquare?(8*n+1) => false
-- Both previous tests from Damgard & Landrock
currPrime:=smallPrimes(mn+10)
probablySafe:=tenPowerTwenty
while count2Order(k) = 0 or n > probablySafe repeat
currPrime := nextPrime currPrime
probablySafe:=probablySafe*(100::I)
rabinProvesComposite(currPrime,n,nm1,q,k) => return false
true
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
