#### [SOLVED] SICP exercise 1.28 - miller-rabin primality test part II

This is a follow-up to SICP exercise 1.28 - miller-rabin primality test.

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 \mod 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 \\$\mod 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 \mod n\\$,” that is, a number not equal to \\$1\\$ or \\$n-1\\$ whose square is equal to \\$1 \mod 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 \mod 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\\$.

Changes:

• Avoid redundant modulo computations
• Corrected use of base modulo n in expmod to avoid computing extremely large numbers
• for any number greater than 2, prevent use of 1 as random base in the expmod because I think it will always return true when the random chosen number is 1. Is this needed?

While fixing my previous code, I already saw a procedure with recursive process that fixed all my problems above. I can't really call it my own, so to keep the spirit of the exercise, I rewrote my horrible recursive process code and turned it into a procedure that generates an iterative process.

Please review 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)
(if (and (= a 1)
(> n 2))
(miller-rabin-test n)
(= (expmod a (- n 1) 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)))
``````

Did I improve on my previous code? Did I follow all the requirements in the exercise this time? How can I improve this code and make it faster?

#### 1 comments #### @Will Ness 2016-09-01 11:27:24

Stylistically, I'd write it this way:

``````;; expmode b e m = b^e modulo m
(define (expmod b e m)
(define (expmod-iter acc b e)      ; iterative accumulation
(define bsq (remainder (* b b) m))
(cond ((= e 0) acc)
((and (not (= b (- m 1)))
(not (= b 1))
(= bsq 1))
0)
((even? exp)
(expmod-iter acc bsq (/ e 2)))
(else
(expmod-iter (remainder (* acc b) m)
b
(- e 1)))))
(expmod-iter 1 b e))               ; initial accumulator = 1

(define (miller-rabin-test n)
(define (try-it b)
(if (and (= b 1)
(> n 2))
(miller-rabin-test n)
(= (expmod b (- n 1) n)
1)))
(try-it (random 1 n)))

(define (fast-prime? n times)
(or (= times 0)
(and (> times 0)
(miller-rabin-test n)
(fast-prime? n (- times 1)))))
``````

You've corrected the error of not taking the remainder of the square.

There's no need to define a function `square` just to save one call to `*`.

You've converted your recursive `expmod` into iterative code; although I wouldn't call the former "horrible" since its complexity is only logarithmic, so recursion depth is kept in check.

Assuming you're using Racket, `(+ 1 (random (- n 1)))` can be written simply `(random 1 n)`.

You've kept the awkward encoding for `fast-prime?` which is more naturally coded directly with the logical connectives.

Will think over some more with regards to its correctness, that you ask about.

### [SOLVED] Writing a product() function analogous to sum

• 2011-03-30 02:49:42
• jaresty
• 932 View
• 0 Score
• 1 Answer
• Tags:   lisp scheme