; Return base^exp mod m ; or 0 if a non-trivial root of 1 mod m is found (define (expmod base exp m) ; Returns base^exp mod m if base^(exp/2) is not a non-trivial root (define (exp-if-only-trivial-roots) (define x (expmod base (/ exp 2) m)) (define y (remainder (square x) m)) ; Check for not trivial square root (if (and (= y 1) (not (or (= x 1) (= x (- m 1))))) 0 y)) (cond ((= exp 0) 1) ((even? exp) (exp-if-only-trivial-roots)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (miller-rabin-test n) (define (try-it a) (= (expmod a (- n 1) n) 1)) ; (random i) returns integer in range [0, i - 1] (try-it (+ 1 (random (- n 1))))) (define (prime? n times) (cond ((= times 0) #t) ((miller-rabin-test n) (prime? n (- times 1))) (else #f))) (filter (lambda (n) (prime? n 100)) '(561 1105 1729 2465 2821 6601))