2 ALGORITHMS FOR MODULAR EXPONENTIATION USING NONSTANDARD ARITHMETICS

Two new algorithms for performing modular exponentiation are suggested . Nonstandard number systems are used. The first algorithm is based on the representing the exponent as a sum of generalized Fibonacci numbe rs. This representation is known as Zeckendorf representation. When pr ecomputing is allowed the resulting algorithm is more efficient than t he classical binary algorithm, but requires more memory. The second al gorithm is based on a new number system, which is called hybrid binary -ternary number system (HBTNS). The properties of the HBTNS are invest igated. With or without precomputing the resulting algorithm for modul ar exponentiation is superior to the classical binary algorithm. A con jecture is made that if more bases are used asymptotically optimal alg orithm can be obtained. Comparisons are made and directions for future research are given.