A SURVEY OF FAST EXPONENTIATION METHODS

Authors
Citation
Dm. Gordon, A SURVEY OF FAST EXPONENTIATION METHODS, Journal of algorithms, 27(1), 1998, pp. 129-146
Citations number
32
Categorie Soggetti
Mathematics,"Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods
Journal title
ISSN journal
01966774
Volume
27
Issue
1
Year of publication
1998
Pages
129 - 146
Database
ISI
SICI code
0196-6774(1998)27:1<129:ASOFEM>2.0.ZU;2-L
Abstract
Public-key cryptographic systems often involve raising elements of som e group (e.g., GF(2(n)), Z/NZ, or elliptic curves) to large powers. An important question is how fast this exponentiation can be done, which often determines whether a given system is practical. The best method for exponentiation depends strongly on the group being used, the hard ware the system is implemented on, and whether one element is being ra ised repeatedly to different powers, different elements are raised to a fixed power, or both powers and group elements vary. This problem ha s received much attention, but the results are scattered through the l iterature. In this paper we survey the known methods for fast exponent iation, examining their relative strengths and weaknesses. (C) 1998 Ac ademic Press.