# [plt-scheme] Implementing Rabin-Miller

 From: John Clements (clements at brinckerhoff.org) Date: Tue Oct 15 14:47:19 EDT 2002 Previous message: [plt-scheme] Implementing Rabin-Miller Next message: [plt-scheme] Implementing Rabin-Miller Messages sorted by: [date] [thread] [subject] [author]

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

 Posted on the users mailing list. Previous message: [plt-scheme] Implementing Rabin-Miller Next message: [plt-scheme] Implementing Rabin-Miller Messages sorted by: [date] [thread] [subject] [author]