V. Dimitrov et T. Cooklev, 2 ALGORITHMS FOR MODULAR EXPONENTIATION USING NONSTANDARD ARITHMETICS, IEICE transactions on fundamentals of electronics, communications and computer science, E78A(1), 1995, pp. 82-87
Citations number
NO
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
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.