Spectacular Exponents: A semi modular Approach to Fast Exponentiation

  • Robert Valenza Claremont McKenna College
Keywords: Integer Exponentiation, Modular Exponentiation, Chinese Remainder Theorem, Garner’s Algorithm, Generating Functions.

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.    

References

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.

Published
2019-06-04
How to Cite
Valenza, R. (2019). Spectacular Exponents: A semi modular Approach to Fast Exponentiation. JOURNAL OF ADVANCES IN MATHEMATICS, 16, 8430- 8448. https://doi.org/10.24297/jam.v16i0.8301
Section
Articles