Exercise 1.27 asks us to demonstrate that the first six Carmicheal numbers (561, 1105, 1729, 2465, 2821, and 6601) really do fool the Fermat test. We're to write a procedure that takes an integer n and tests whether a

^{n}is congruent to a modulo n for every value less than n, then test the procedure on each of the Carmichael numbers listed.

The

`fermat-test`

procedure that we first saw in exercise 1.24 is a good starting point.`(define (fermat-test n)`

(define (try-it a)

(= (expmod a n n) a))

(try-it (+ 1 (random-integer (- n 1)))))

Let' start by modifying this procedure so that we pass it the value to test, instead of generating a random value.

`(define (fermat-test n a)`

(= (expmod a n n) a))

Now we just need to define a new procedure that will call this one for every value less than the one we want to test. If

`fermat-test`

passes for all values tested we should return `true`

, but if it fails for any value we should return `false`

. Here is the complete code listing for the exercise.`(define (square x)`

(* x x))

(define (even? n)

(= (remainder n 2) 0))

(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 a)

(= (expmod a n n) a))

(define (fermat-full n)

(define (iter a)

(cond ((= a 1) #t)

((not (fermat-test n a)) #f)

(else (iter (- a 1)))))

(iter (- n 1)))

Prime numbers will legitimately pass this test, and Carmichael numbers will fool it. All other composites should fail. You can test out a few primes and composites in a Scheme interpreter to make sure it works as described. Here's the output for the first six Carmichael numbers.

`> (fermat-full 561)`

#t

> (fermat-full 1105)

#t

> (fermat-full 1729)

#t

> (fermat-full 2465)

#t

> (fermat-full 2821)

#t

> (fermat-full 6601)

#t

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

## No comments:

Post a Comment