I played a little more with PRIMES, more precisely with
rabinProvesComposite and prime?
There are at least two things unclear. For example, we have (globally)
rootsMinus1:Set I := empty()
-- used to check whether we detect too many roots of -1
count2Order:Vector NonNegativeInteger := new(1,0)
-- used to check whether we observe an element of maximal two-order
rootsMinus1 is the set {b^(q 2^(j-1)) : b^(q 2^j) = -1 mod n}
Clearly, when rootsMinus1 contains more than two elements, then n cannot
be a prime. However, I could not find *any* number such that this
condition would be triggered in rabinProvesComposite.
count2Order(j) = #{b: b^(q 2^(j-1)) = -1 mod n}
When count2Order(k)>0 (remember q 2^k = n-1) then n must be prime, since
then b has order n-1. However, count2Order(j) for smaller j seems to be
unused, and I can't think of a good use for them. Moreover, the first
test count2Order(k)>0 appears very late. Testing earlier seems to be
*very* effective.
Can I commit? (after a little more testing
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 one? t or t = nm1 then
false
else
for j in 1..k-1 repeat
t := mulmod(t, t, n)
-- we have squared someting not -1 and got 1
one? t => return true
-- we encountered a -1 before the very end
t = nm1 => return false
-- all but possibly b^(2^k*q) are different from +1 and -1
true
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)
if t = nm1 then count2Order(1) := count2Order(1)+1
-- neither of these cases tells us anything
if one? t or t = nm1 then
false
else
for j in 1..k-1 repeat
oldt := t
t := mulmod(t, t, n)
-- we have squared someting not -1 and got 1
one? t => return true
t = nm1 =>
rootsMinus1 := union(rootsMinus1, oldt)
# rootsMinus1 > 2 =>
return true -- Z/nZ can't be a field
count2Order(j+1) := count2Order(j+1)+1
return false
-- all but possibly b^(2^k*q) are different from +1 and -1
true
prime? n ==
n < two => false
n < nextSmallPrime => member?(n, smallPrimes)
-- not one? gcd(n, productSmallPrimes) => false
not (gcd(n, productSmallPrimes) = 1) => 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
(count2Order(k) > 0) => return true
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
if n <= probablySafe then
print("count2Order"::OutputForm)
print(count2Order::OutputForm)
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.
