[plt-scheme] Implementing Rabin-Miller

On Tuesday, October 15, 2002, at 04:09  PM, Paulo Jorge O. C. Matos 
wrote:

> (1)  Choose a random number, a, such that a is less than p.
> (2)  Set j = 0 and set z = am mod p.
> (3)  If z = 1, or if z = p - 1, then p passes the test and may be 
> prime. (4)  If j > 0 and z = 1, then p is not prime.
> (5)  Set j = j + 1. If j < b and z ? p - 1, set z = z2 mod p and go 
> back to step (4). If z = p - 1, then p passes the test and may be 
> prime.
> (6)  If j = b and z ? p - 1, then p is not prime.
>

This looks like a terrible specification of an algorithm. Rewrite it 
like this:

evaluate the function iterate(0,am mod p):

iterate(j,z) =
   - if z=1 then
     - if j=0, return #t, otherwise #f
   - if z=p-1, return #t
   - if j = b, return #f
   - otherwise, recur with iterate(j+1,z2 mod p)

Due to a dreadful spec, I may be off in the boundary condition for j.  
Frankly, it might be easier to read in scheme:

(let iterate ([j 0] [z (modulo (* a m) p)])
   (cond [(= z 1) (= j 0)]
         [(= z (- p 1)) #t]
         [(= j b) #f]
         [else (iterate (+ j 1)) (modulo (* z z) p)]))

john