Exercise 1.28 of SICP

Exercise 1.28: One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat’s Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the (n – 1)st power is congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a random number an-1 in this way will reveal a nontrivial square root of 1 modulo n. (This is why the Miller-Rabin test cannot be fooled.) Modify the expmod procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a procedure analogous to fermat-test. Check your procedure by testing various known primes and non-primes. Hint: One convenient way to make expmod signal is to have it return 0.

Carmichael Numbers: 561, 1105, 1729, 2465, 2821, 6601
Primes: 2, 3, 10169, 31337, 1000249, 382176531747930913347461352433
Non-primes: 6, 27, 49, 1024

> (fast-prime? 561 10)
#f
> (fast-prime? 1105 10)
#f
> (fast-prime? 1729 10)
#f
> (fast-prime? 2465 10)
#f
> (fast-prime? 2821 10)
#f
> (fast-prime? 6601 10)
#f
> (fast-prime? 2 10)
#t
> (fast-prime? 3 10)
#t
> (fast-prime? 10169 10)
#t
> (fast-prime? 31337 10)
#t
> (fast-prime? 1000249 10)
#t
> (fast-prime? 382176531747930913347461352433 10)
#t
> (fast-prime? 6 10)
#f
> (fast-prime? 27 10)
#f
> (fast-prime? 49 10)
#f
> (fast-prime? 1024 10)
#f

Leave a Reply