Spectacular Exponents: A semi modular Approach to Fast Exponentiation
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.
Gordon, Daniel M. “A survey of fast exponentiation methods.” Journal of Algorithms, Vol. 27, No. 1 (April 1998), pp. 129–146.
Bernstein, Daniel J. “Detecting perfect powers in essentially linear time.” Mathematics of Computation, Vol. 67, No. 223, July 1988, pp. 1253–1283.
Tucker, Alan. Applied Combinatorics (Second Edition), John Wiley & Sons, New York, 1984.
Lang, Serge. Algebra (Revised Third Edition). Springer Graduate Texts in Mathematics 211, New York, 2002.
Knuth, Donald E. The Art of Computer Programming, Volume 2: Semi numerical Algorithms (Second Edition). Addison-Wesley, Reading, Massachusetts, 1981.
Cross, James T. “The Euler ? -function in the Gaussian integers.” The American Mathematical Monthly, Vol. 90, No. 8 (Oct. 1983), pp. 518–528.
Copyright (c) 2019 Robert Valenza
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors retain the copyright of their manuscripts, and all Open Access articles are distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided that the original work is properly cited.