36 lines
765 B
Racket
36 lines
765 B
Racket
|
#lang racket ; needed for true / false
|
||
|
|
|
||
|
|
(define (square n)
|
||
|
|
(* n n))
|
||
|
|
|
||
|
|
(define (expmod base exp m)
|
||
|
|
(cond ((= exp 0) 1)
|
||
|
|
((even? exp)
|
||
|
|
(remainder (square (expmod base (/ exp 2) m))
|
||
|
|
m))
|
||
|
|
(else
|
||
|
|
(remainder (* base (expmod base (- exp 1) m))
|
||
|
|
m))))
|
||
|
|
|
||
|
|
(define (fermat-test n smaller-n)
|
||
|
|
(define (try-it a)
|
||
|
|
(= (expmod a n n) a))
|
||
|
|
(cond ((= smaller-n 1) true)
|
||
|
|
((try-it smaller-n) (fermat-test n (- smaller-n 1)))
|
||
|
|
(else false)))
|
||
|
|
|
||
|
|
(define (is-carmichael-prime? n)
|
||
|
|
(fermat-test n (- n 1)))
|
||
|
|
|
||
|
|
561
|
||
|
|
(is-carmichael-prime? 561)
|
||
|
|
1105
|
||
|
|
(is-carmichael-prime? 1105)
|
||
|
|
1729
|
||
|
|
(is-carmichael-prime? 1729)
|
||
|
|
2465
|
||
|
|
(is-carmichael-prime? 2465)
|
||
|
|
2821
|
||
|
|
(is-carmichael-prime? 2821)
|
||
|
|
6601
|
||
|
|
(is-carmichael-prime? 6601)
|