Description
The expmod function in §1.2.6 uses a subtlety. It is perhaps not immediately clear to (even careful) readers that for any three positive integers a, b, c, (ab) % c equals (r1r2) % c (where r1 = a % c and r2 = b % c).
Perhaps the main discussion around the function expmod should encourage readers to arrive at the above result (either through a footnote or through an exercise). Here is my humble attempt.
Relatedly, in exercise 1.25, we ask if Alyssa is correct in saying that fast_expt can effectively replace expmod. Whereas the answer provided there is correct, I believe that we need to establish if the remainder is not preserved in a two's complement notation even when the silent overflow occurs. I guess it is not preserved, and, as such, it is better to do r1r2 % c to reduce the likelihood of an overflow. I just feel that for the sake of completeness, we should mention this.
Another question: In the case of an odd exponent, shouldn't expmod be modified to
: ((base % m) * expmod(base, exp - 1, m))) % m;
(just for the sake of uniformity)?