Spectacular Exponents: A semi modular Approach to Fast Exponentiation

Abstract

This paper introduces a computational scheme for calculating the exponential bw where b and w are positive integers. This two-step method is based on elementary number theory that is used routinely in this and similar contexts, especially the Chinese remainder theorem (CRT), Lagrange’s theorem, and a variation on Garner’s algorithm for inverting the CRT isomorphism. We compare the performance of the new method to the standard fast algorithm and show that for a certain class of exponents it is significantly more efficient as measured by the number of required extended multiplications.