Quite a while ago, I presented a fast exponentiation algorithm that uses the binary decomposition of the exponent to perform
products to compute
.
While discussing this algorithm in class, a student asked a very interesting question: what’s special about base 2? Couldn’t we use another base? Well, yes, yes we can.