schemeprimessicpmodular-arithmeticprimality-test# Miller-Rabin test (SICP 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

nis a prime number andais any positive integer less thann, thenaraised to the(n - 1)st power is congruent to1modulon.To test the primality of a number

nby the Miller-Rabin test, we pick a random numberaless thannand raiseato the(n - 1)st power modulonusing the`expmod`

procedure. However, whenever we perform the squaring step in`expmod`

, we check to see if we have discovered a “nontrivial square root of1modulon,” that is, a number not equal to1orn - 1whose square is equal to1modulon.It is possible to prove that if such a nontrivial square root of

1exists, thennis not prime. It is also possible to prove that ifnis an odd number that is not prime, then, for at least half the numbersa < n, computingain this way will reveal a nontrivial square root of^{n-1}1modulon. (This is why the Miller-Rabin test cannot be fooled.)Modify the

`expmod`

procedure to signal if it discovers a nontrivial square root of1, 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.

This is what I have so far.

```
(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))
(define (expmod-signal b n m)
(define (check a)
(and (not (= a 1))
(not (= a (- n 1)))
(= (square a) (remainder 1 n))))
(cond ((= n 0) 1)
((check b) 0)
((even? n) (remainder (square (expmod-signal b (/ n 2) m)) m))
(else (remainder (* b (expmod-signal b (- n 1) m)) m))))
(define (miller-rabin n)
(define (fail? n a)
(or (= n 0) (not (= n a))))
(define (try a)
(cond ((= a 1) #t)
((fail? (expmod-signal a (- n 1) n) a) #f)
(else (try (- a 1)))))
(try (- n 1)))
```

I think I implemented `miller-rabin`

correctly but I don't understand how the modified `expmod`

is supposed to work. Do you check the number before the square or after the square? I don't know from reading the question.

Solution

I solved this by using the original definition of `expmod`

inside of `expmod-signal`

. Somewhere in my tests, `expmod-signal`

was naturally returning zero and messing with the tests. I misunderstood the check function, "whose square is equal to 1 modulo n" means check if `a^2 % m = 1`

. The way this check function works is to return 0 if the argument is a non-trivial square root of 1 mod n, and return the argument otherwise. If it returns zero, the zero propagates through the remainder of `expmod-signal`

and is returned.

```
(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
(else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (expmod-signal b n m)
(define (check a)
(if (and (not (= a 1))
(not (= a (- n 1)))
(= (remainder (square a) n) 1))
0
a))
(cond ((= n 0) 1)
((even? n) (remainder (square (check (expmod b (/ n 2) m))) m))
(else (remainder (* b (expmod b (- n 1) m)) m))))
(define (miller-rabin n)
(define (fail? a)
(or (= a 0) (not (= a 1))))
(define (try a)
(cond ((= a 1) #t)
((fail? (expmod-signal a (- n 1) n)) #f)
(else (try (- a 1)))))
(try (- n 1)))
```

- How to create Alist from List using syntax-rules in Scheme?
- Exercise 12.10 from the book Scheme and the art of programming
- Anonymous lambdas directly referring to themselves
- Why can't a Scheme macro with the name "if" be defined?
- How to implement "if" in normal order in Scheme?
- Map-reduce functional outline
- How to use let-values in Gambit Scheme?
- Execute command line from Scheme (Guile)
- How do I define a sub environment in scheme?
- Sources for learning about Scheme Macros: define-syntax and syntax-rules
- What is "Call By Name"?
- DrRacket's call/cc
- Racket: Conditional Statements Not Matching String Equality in Gambling Simulation"
- What's wrong with this coin change python implementation?
- Encode "ä", "ö", "ü" and "ß" in scheme (get german text from file)
- Using AND with the apply function in Scheme
- Combination of list-ref and index-of in racket
- How to undefine a variable in Scheme?
- Running Scheme from the command line
- Function that splits word
- How does the yin-yang puzzle work?
- Dr Racket Recursing Without Returning Inital Parent Node Within Function
- Chez Scheme FFI Procedure Doesn't Work After Change to Apple Silicon
- How do we convert this Scheme (Lisp) function into C#
- What is #~ in scheme?
- Racket : Run scheme file in terminal and show result
- Recursive numeric equality in Scheme
- Under any Scheme standard, is (let (x y z) x) valid code?
- Iterate through the letters of the alphabet in Racket
- What do Lisp macros have over functions that optionally evaluate their arguments?