May 1, 2009
Although the math looks difficult, the code is quite straight forward.
Check? calculates r and s in the outer loop, checks if as is 1 modulo n, and then the inner loop checks the other condition for each j from 0 to r-1.
(define (check? a n)
(let loop ((r 0) (s (- n 1)))
(if (even? s) (loop (+ r 1) (/ s 2))
(if (= (expm a s n) 1) #t
(let loop ((j 0) (s s))
(cond ((= j r) #f)
((= (expm a s n) (- n 1)) #t)
(else (loop (+ j 1) (* s 2)))))))))
prime? tests a few boundary conditions and performs fifty random calls to
> (prime? (- (expt 2 89) 1))
You can run this code at http://codepad.org/rSDxFrZn.
Pages: 1 2