; Miller-Rabin prime tester (let ((mod-exp (fileVal "mod-exp"))) (let ((base (lambda (a n) (or (= n 2) (= n 3) (let* ((nm1 (- n 1))(pr (let z ((d nm1)(k 0))(if (odd? d)(cons d k) (z (/ d 2)(+ k 1))))) (d (car pr))(s (cdr pr))) (let lp ((r 0)(y (mod-exp a d n))) (or (and (= r 0)(= y 1)) (= y nm1) (and (< r (- s 1))(lp (+ r 1)(modulo (* y y) n)))))))))) (lambda (sy) (cdr (assq sy (list (cons 'base base) (cons 'multi (lambda (n) (let ((st ((fileVal "RC4") "Falcon"))) (lambda (c) (let ((rp ((st 'rbi) (- c 3)))) ; None of -1, 0, 1 are appropriate as probes. (let p ((n n)) (or (zero? n) (and (base (+ 2 (rp)) c) (p (- n 1)))))))))))))))) ; Demos (((fileVal "Miller-Rabin") 'base) 675938 1000000000001) => #f ((((fileVal "Miller-Rabin") 'multi) 20) 6700417) -> #t ; false witness: (((fileVal "Miller-Rabin") 'base) 4293918721 (* 641 6700417)) => #t ; The small integers: (let ((DoL ((fileVal "Do") 'DoL))(b ((fileVal "Miller-Rabin") 'base))) (DoL 20 (lambda (n) (let ((n (+ n 4))) (cons n (DoL (- n 3) (lambda (k) (let ((k (+ k 2))) (b k n))))))))) ; Above finds no flase witnesses below 23. ; Some larger composits: (let* ((b ((fileVal "Miller-Rabin") 'base)) (t (lambda (c) (let r ((n (- c 1))) (or (= n 1) (begin (if (b n c) (begin (write (list n c)) (newline))) (r (- n 1)))))))) (map t (list 21 (* 19 53) (* 419 631) (* 641 6700417) ; (expt 2 38) )))