ex_1_28.clj

(ns sicp.chapter-1.part-2.ex-1-28)

; 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 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.

; TODO: Implement Miller-Rabin test. See https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
; One of solution is https://github.com/qiao/sicp-solutions/blob/master/chapter1/1.28.scm