Wednesday, June 3, 2009

Ex-1.27

(define (fermat-test-1-to-n n)
(define (try-it a)
(= (expmod a n n) a))
(define (fermat-iter a)
(cond ((= a n) #f)
((try-it a) #t)
(else (fermat-iter (+ a 1)))))
(fermat-iter 1))

1 ]=> (fermat-test-1-to-n 561)
;Value: #t
1 ]=> (fermat-test-1-to-n 1105)
;Value: #t
1 ]=> (fermat-test-1-to-n 1729)
;Value: #t
1 ]=> (fermat-test-1-to-n 2465)
;Value: #t
1 ]=> (fermat-test-1-to-n 2821)
;Value: #t
1 ]=> (fermat-test-1-to-n 6601)
;Value: #t

Its clear that these number fool the fermat test as all of them are passing the fermat test but none of them are prime.

No comments:

Post a Comment