15 lines
473 B
Scheme
15 lines
473 B
Scheme
(define (expmod base exp m)
|
|
(remainder (fast-expt base exp) m))
|
|
|
|
(define (fast-expt b n)
|
|
(cond ((= n 0) 1)
|
|
((even? n) (square (fast-expt b (/ n 2))))
|
|
(else (* b (fast-expt b (- n 1))))))
|
|
|
|
(define (even? n)
|
|
(= (remainder n 2) 0))
|
|
|
|
; This appears to be equivalent to calculating the exponent modulo m with the
|
|
; exception that for large numbers, fast-expt will get very large before
|
|
; calculating the modulus, so it is probably not suitable for a fast prime tester.
|