CODEWITHSUNDEEP
schemesicp
GiAlien
GiAlien

Reputation: 33

Is this code for Miller-Rabin test wrong? (answer for the exercise for 1.28 in SICP)

I was trying to solve exercise 1.28 in SICP, about Miller-Rabin algorithm, after which I found an answer online, but I think the answer was wrong. I come to ask if it's wrong.

He checks if (remainder (square base) m)=1 while doing expmod loops. However, when doing loops the base and m will stay constantly, which means he is doing the same check, and it's not what the Miller-Rabin Test want to do.

(define (expmod base exp m)
  (cond ((= exp 0)
         1)
        ((nontrivial-square-root? base m) 
         0)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(define (nontrivial-square-root? a n)
  (and (not (= a 1))
       (not (= a (- n 1)))
       (= 1 (remainder (square a) n))))

if n=k*2^c, I think we should check if (remainder (a^(k*2*(c-1))) n)=1.

Upvotes: 3

Views: 100

Answers (1)

Jodast
Jodast

Reputation: 1299

That is what it is supposed to be doing. The procedure expmod is supposed to compute the exponential of a number modulo another number, the only difference this time is that you check for a nontrivial square root every time it recurses. m will stay constant during the expmod procedure, and the miller-rabin procedure you write will run expmod with a random number m every time.

Happy coding!

By the way, good luck with SICP! I'm on excersise 2.45 right now, it gets easier (although there are some very abstract concepts).

Upvotes: 1

Related Questions