You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
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) |