**Exercise 1.25:** Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written

1 2 |
(define (expmod base exp m) (remainder (fast-expt base exp) m)) |

Is she correct? Would this procedure serve as well for our fast prime tester? Explain.

While the procedure is mathematically accurate and would produce the right results, fast-expt would produce enormous numbers that would then have to be reduced modulo m. For example:

(expmod 2 10 7)

(remainder (fast-expt 2 10) 7)

(remainder 1024 7)

The 1024 might not seem so bad at first.

(expmod 2 100 7)

(remainder (fast-expt 2 10) 7)

(remainder 1267650600228229401496703205376 7)

That’s a bit excessive.

The version bellow keeps the number in check.

1 2 3 4 5 6 7 8 |
(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)))) |

I am taking some liberty here in skipping a few minor steps.

(expmod 2 10 7)

(remainder (square (expmod 2 5 7)) 7)

(remainder (square (remainder (* 2 (expmod 2 4 7)) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square (expmod 2 2 7)) 7)) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square (remainder (square (expmod 2 1 7)) 7)) 7) 7) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square (remainder (square (remainder (* 2 1) 7)) 7)) 7)) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square (remainder (square (remainder 2 7)) 7)) 7)) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square (remainder (square 2) 7)) 7)) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square (remainder 4 7)) 7)) 7)) 7)

(remainder (square (remainder (* 2 (remainder (square 4) 7)) 7)) 7)

(remainder (square (remainder (* 2 2) 7)) 7)

(remainder (square (remainder 4 7)) 7)

(remainder (square 4) 7)

2

The key difference is that at no point do any of the numbers grow to be much larger than the base.