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
shouldn't the penultimate line read
not (oldt = nm1) => return true
??? We know that n is composite if
p^(2^(j+1)*q) is different from -1 and +1 but
p^(2^k*q) = -1
Martin
PS: p is confusing: it's not necessarily a prime, I vote for changing it
to b. Also, the loop would be better to understand if it read
for j in 2..k repeat
--
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.
