### SICP exercise 1.28 - Miller Rabin Primality Test

Posted:

**Fri Aug 26, 2016 2:49 am**Hi, I'm new here.

Can anyone review my code? This is exercise 1.28 from SICP.

Description:

"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 a < n and raise a to the n-1-st power modulo n using the expmod procedure. However, whenever we perform the squaring step in expmod, we check to see if we have discovered a “nontrivial square root of 1 modulo n,” that is, a number not equal to 1 or n-1 whose square is equal to 1 modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a < n, computing a^n-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."

https://mitpress.mit.edu/sicp/chapter1/node17.html

Here is my code:

(define (square x) (* x x))

(define (expmod base exp m)

(define (expmod-iter a base exp)

(define squareMod (remainder (square base) m))

(cond ((= exp 0) a)

((and (not (= base (- m 1)))

(not (= base 1))

(= squareMod 1))

0)

((even? exp)

(expmod-iter

a

squareMod

(/ exp 2)))

(else

(expmod-iter

(remainder (* a base) m)

base

(- exp 1)))))

(expmod-iter

1

base

exp))

(define (miller-rabin-test n)

(define (try-it a)

(= (expmod a n n) 1))

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

(define (fast-prime? n times)

(cond ((= times 0) true)

((miller-rabin-test n)

(fast-prime? n (- times 1)))

(else false)))

http://paste.lisp.org/display/323708

Did I follow the exercise? Is this correct? Are there bugs? Thanks for any feeback!

Can anyone review my code? This is exercise 1.28 from SICP.

Description:

"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 a < n and raise a to the n-1-st power modulo n using the expmod procedure. However, whenever we perform the squaring step in expmod, we check to see if we have discovered a “nontrivial square root of 1 modulo n,” that is, a number not equal to 1 or n-1 whose square is equal to 1 modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a < n, computing a^n-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."

https://mitpress.mit.edu/sicp/chapter1/node17.html

Here is my code:

(define (square x) (* x x))

(define (expmod base exp m)

(define (expmod-iter a base exp)

(define squareMod (remainder (square base) m))

(cond ((= exp 0) a)

((and (not (= base (- m 1)))

(not (= base 1))

(= squareMod 1))

0)

((even? exp)

(expmod-iter

a

squareMod

(/ exp 2)))

(else

(expmod-iter

(remainder (* a base) m)

base

(- exp 1)))))

(expmod-iter

1

base

exp))

(define (miller-rabin-test n)

(define (try-it a)

(= (expmod a n n) 1))

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

(define (fast-prime? n times)

(cond ((= times 0) true)

((miller-rabin-test n)

(fast-prime? n (- times 1)))

(else false)))

http://paste.lisp.org/display/323708

Did I follow the exercise? Is this correct? Are there bugs? Thanks for any feeback!