[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:
>
Taken from Applied Cryptography by Scheneier (one of the best books on
cryptography).
> 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)
Are you sure this is the algorithm specified above? Damn, I'll have to
look at it more carefully. :)
>
> 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)]))
>
Just for the record, my last version was:
(define isprime?
(lambda (p)
(let* ((b (get-b p))
(m (/ (- p 1) (expt 2 b)))
(a (+ 1 (random (if (> p 2147483647) 2147483646 (- p 1)))))
(z (modulo (expt a m) p)))
(printf "z = ~a, a = ~a, m = ~a, b = ~a~n" z a m b)
(if (or (= z 1)
(= z (- p 1)))
#t
(let loop ((nz z)
(j 0))
(cond ((and (> j 0)
(= nz 1))
(printf "j > 0 and z = 1~n")
#f)
((and (< (+ j 1) b)
(not (= nz (- p 1))))
(printf "looping z = ~a, j = ~a~n" nz j)
(loop (modulo (* nz nz) p)
(+ j 1)))
((= nz (- p 1))
(printf "z = p - 1~n")
#t)
((and (= j b)
(not (= nz (- p 1))))
(printf "j = b and z =/= p - 1~n")
#f)
(else (error "Condition not expected."))))))))
> john
>
>
I'll take a look at your implementation, thanks a lot.
Best regards,
--
Paulo J. Matos : pocm(_at_)mega.ist.utl.pt
Instituto Superior Tecnico - Lisbon
Software & Computer Engineering - A.I.
- > http://mega.ist.utl.pt/~pocm
---
Yes, God had a deadline...
So, He wrote it all in Lisp!