[plt-scheme] Implementing Rabin-Miller
1. You can use call-with-current-continuation (call/cc) in Scheme to achieve
return/goto control effects, but it is very rare that this is an elegant way
to structure your program.
2. It is true that algorithms are often specified with procedural
pseudocode; however, especially for discrete numerical algorithms, there is
almost always a more elegant functional expression. I attached an old
implementation of Rabin-Miller I had lying around, although it doesn't look
much like what you gave.
3. The particular procedural description of Rabin-Miller you gave is really
confusing. The basic algorithm is much easier to understand when specified
declaratively.
4. Last August, three Indian researchers discovered a deterministic
polynomial-time algorithm to test primality, which is not terribly more
complicated than Rabin-Miller. http://www.cse.iitk.ac.in/news/primality.html
-Mike
----- Original Message -----
From: "Paulo Jorge O. C. Matos" <pocm at mega.ist.utl.pt>
To: <plt-scheme at qua.cs.brown.edu>
Sent: Tuesday, October 15, 2002 4:09 PM
Subject: [plt-scheme] Implementing Rabin-Miller
> For list-related administrative tasks:
> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> Hi all,
>
> I've been sometimes confronted with some messy situations in scheme. Two
> are of special importance. Sometimes while implementing algorithms
> (usually specified in an imperative pseudo-language) there are steps
> like this: If <condition> go to step 3 else return <value>. There is no
> goto blabla or return-from in Scheme. I'm curious how you would
> implement the following simple algorithm in Scheme. I've done it as
> follows (extremely ugly, I agree):
> (define isprime?
> ;Rabin-Miller algorithm
> (lambda (p)
> (let* ((b (get-b p))
> (m (/ (- p 1) (expt 2 b)))
> (a (random (if (> p 2147483647) 2147483647 p)))
> (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)))
> (begin
> (printf "Step 1: z = ~a so p may be prime.~n" z)
> #t) ;p MAY BE prime!
> (let loop ((j 0))
> (printf "Step 4, setting j = 0 and z = z^2 mod p.~n")
> (if (and (= z 1)
> (> j 0))
> #f ;p is SURELY not prime
> (begin
> (set! j (+ j 1))
> (if (and (< j b)
> (not (= z (- p 1))))
> (begin
> (set! z (modulo (* z z) p))
> (loop j))
> (if (= z (- p 1))
> #t
> (if (and (= j b)
> (not (= z (- p 1))))
> #f))))))))))
>
> The rabin-miller is as follows:
>
> Choose a random number, p, to test. Calculate b, where b is the number
> of times 2 divides p - 1 (i.e., 2b is the largest power of 2 that
> divides p - 1). Then calculate m, such that p = 1 + 2b *m.
>
> (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.
>
>
> 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!
>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: rabin-miller.scm
Type: application/octet-stream
Size: 1436 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20021015/fa1731d7/attachment.obj>