Skip to content

Instantly share code, notes, and snippets.

@cky cky/miller-rabin.rkt
Last active Jun 2, 2016

Embed
What would you like to do?
My Miller-Rabin implementation (see http://codereview.stackexchange.com/a/129991/216 for context)
#lang racket
(define (expmod base exp m)
(let recur ([exp exp])
(cond [(zero? exp) 1]
[(even? exp) (let* ([prev (recur (quotient exp 2))]
[result (modulo (sqr prev) m)])
(if (and (< 1 prev (sub1 m))
(= result 1))
0
result))]
[else (modulo (* base (recur (sub1 exp))) m)])))
(define (composite? n [trials 100])
(for/first ([i (in-range trials)]
#:unless (= (expmod (random 2 (min (sub1 n) 4294967087))
(sub1 n) n) 1))
#t))
@cky

This comment has been minimized.

Copy link
Owner Author

cky commented Jun 2, 2016

BTW, the (min (sub1 n) 4294967087), as opposed to just (sub1 n), is to prevent random from issuing a domain error.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.