1.25 Exercise 1.25

She is correct that you can compute expmod this way, but it requires a bit of knowledge to be sure of. The long-form expmod takes the remainder of every recursive call to expmod modulo m, while Alyssa’s expmod only takes the remainder once, after the exponent has been calculated. Importantly, it is true that taking the remainder once after exponentiation or multiple times during its calculation does not change the result.

However, because Alyssa’s procedure takes the remainder of a potentially much larger number, it may be the case that this is slower than the original procedure, which computes more, simpler remainders.

TODO: Show test results