expmod Base Exp M = {eq Exp 0 = #y
;even? Exp = rem (expmod Base Exp/2 M)^2 M)
; #y = rem Base*(expmod Base Exp-1 M) M}
prime? K N
= lehmannTest:<Tries A = X:(expmod A (N-1)/2.0 N)
= {eq Tries 0 = #y
;{eq X 1; eq X (mod -1 N)} = r Tries-1 (rand N)+1
;#t = #f}>
= {lt N 2 = #y
;eq N 2 = #n
;even? N = #f
;#t = lehmanTest K (rand N)+1}
(define (square x) (* x x))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))
(define (prime? k n)
(define (lehmann-test tries a)
(let ((x (expmod a (/ (- n 1) 2.0) n)))
(cond ((= tries 0) #t)
((or (= x 1) (= x (modulo -1 n)))
(lehmann-test (- tries 1) (random>0 n)))
(else #f))))
(cond ((< n 2) #f)
((= n 2) #t)
((even? n) #f)
(else (lehmann-test k (random>0 n)))))