Spectacular Exponents: A semi modular Approach to Fast Exponentiation

Authors

  • Robert Valenza Claremont McKenna College

DOI:

https://doi.org/10.24297/jam.v16i0.8301

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.    

Downloads

Download data is not yet available.

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

Issue

Section

Articles