# [plt-scheme] Implementing Rabin-Miller

 From: Paulo Jorge O. C. Matos (pocm at mega.ist.utl.pt) Date: Tue Oct 15 18:34:36 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:
>

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!

```

 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]