Spectacular Exponents: A semi modular Approach to Fast Exponentiation
Keywords:Integer Exponentiation, Modular Exponentiation, Chinese Remainder Theorem, Garner’s Algorithm, Generating Functions.
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.
How to Cite
All articles published in Journal of Advances in Linguistics are licensed under a Creative Commons Attribution 4.0 International License.