; proving primality
(define (expm b e m)
(define (m* x y) (modulo (* x y) m))
(cond ((zero? e) 1)
((even? e) (expm (m* b b) (/ e 2) m))
(else (m* b (expm (m* b b) (/ (- e 1) 2) m)))))
(define (td-factors n)
(let loop ((n n) (x 2) (fs '()))
(cond ((< n (* x x)) (reverse (cons n fs)))
((zero? (modulo n x)) (loop (/ n x) x (cons x fs)))
(else (loop n (+ x 1) fs)))))
(define (prime? n)
(let ((n-1 (- n 1)))
(let loop ((b 2) (qs (td-factors n-1)))
(cond ((not (= (expm b n-1 n) 1)) (loop (+ b 1) qs))
((null? qs) #f)
((not (= (expm b (/ n-1 (car qs)) n) 1)) #t)
(else (loop b (cdr qs)))))))
(display (prime? (- (expt 2 89) 1)))