Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics

Vassil DIMITROV; Todor COOKLEV

Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics

Vassil DIMITROV, Todor COOKLEV

Full Text Views

0

Cite this

Summary :

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 numbers. This representation is known as Zeckendorf representation. When precomputing is allowed the resulting algorithm is more efficient than the classical binary algorithm, but requires more memory. The second algorithm is based on a new number system, which is called hybrid binary-ternary number system (HBTNS). The properties of the HBTNS are investigated. With or without precomputing the resulting algorithm for modular exponentiation is superior to the classical binary algorithm. A conjecture is made that if more bases are used asymptotically optimal algorithm can be obtained. Comparisons are made and directions for future research are given.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.1 pp.82-87

Publication Date: 1995/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section LETTER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Vassil DIMITROV, Todor COOKLEV, "Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics" in IEICE TRANSACTIONS on Fundamentals, vol. E78-A, no. 1, pp. 82-87, January 1995, doi: .
Abstract: 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 numbers. This representation is known as Zeckendorf representation. When precomputing is allowed the resulting algorithm is more efficient than the classical binary algorithm, but requires more memory. The second algorithm is based on a new number system, which is called hybrid binary-ternary number system (HBTNS). The properties of the HBTNS are investigated. With or without precomputing the resulting algorithm for modular exponentiation is superior to the classical binary algorithm. A conjecture is made that if more bases are used asymptotically optimal algorithm can be obtained. Comparisons are made and directions for future research are given.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e78-a_1_82/_p

Copy

@ARTICLE{e78-a_1_82,
author={Vassil DIMITROV, Todor COOKLEV, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics},
year={1995},
volume={E78-A},
number={1},
pages={82-87},
abstract={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 numbers. This representation is known as Zeckendorf representation. When precomputing is allowed the resulting algorithm is more efficient than the classical binary algorithm, but requires more memory. The second algorithm is based on a new number system, which is called hybrid binary-ternary number system (HBTNS). The properties of the HBTNS are investigated. With or without precomputing the resulting algorithm for modular exponentiation is superior to the classical binary algorithm. A conjecture is made that if more bases are used asymptotically optimal algorithm can be obtained. Comparisons are made and directions for future research are given.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Two Algorithms for Modular Exponentiation Using Nonstandard Arithmetics
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 82
EP - 87
AU - Vassil DIMITROV
AU - Todor COOKLEV
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1995
AB - 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 numbers. This representation is known as Zeckendorf representation. When precomputing is allowed the resulting algorithm is more efficient than the classical binary algorithm, but requires more memory. The second algorithm is based on a new number system, which is called hybrid binary-ternary number system (HBTNS). The properties of the HBTNS are investigated. With or without precomputing the resulting algorithm for modular exponentiation is superior to the classical binary algorithm. A conjecture is made that if more bases are used asymptotically optimal algorithm can be obtained. Comparisons are made and directions for future research are given.
ER -