2016-08-20 16:12:42 8 Comments

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?

### Related Questions

#### Sponsored Content

#### 2 Answered Questions

#### 2 Answered Questions

### [SOLVED] SICP - exercise 1.7 better end test for square root approximation

**2017-07-13 18:34:48****morbidCode****253**View**3**Score**2**Answer- Tags: lisp scheme numerical-methods sicp

#### 1 Answered Questions

### [SOLVED] Optimizing Miller-Rabin Primality Test in Python

**2018-03-05 00:32:56****D. Senack****369**View**4**Score**1**Answer- Tags: python performance primes

#### 0 Answered Questions

### Computing nth roots of a number - SICP exercise 1.45

**2016-12-07 16:45:34****morbidCode****103**View**2**Score**0**Answer- Tags: performance functional-programming lisp sicp numerical-methods

#### 2 Answered Questions

### [SOLVED] Large Power Mod - Extreme Efficiency

**2016-09-25 04:06:08****Myridium****147**View**5**Score**2**Answer- Tags: performance haskell mathematics

#### 1 Answered Questions

#### 1 Answered Questions

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

**2016-06-02 17:06:08****morbidCode****192**View**2**Score**1**Answer- Tags: performance primes lisp scheme sicp

#### 3 Answered Questions

#### 2 Answered Questions

### [SOLVED] SICP - exercise 2.20 - same-parity

**2015-12-30 19:15:17****morbidCode****185**View**1**Score**2**Answer- Tags: performance beginner lisp scheme sicp

## 1 comments

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

Stylistically, I'd write it this way:

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.