[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!