FAST EXPONENTIATION METHOD OBTAINED BY FOLDING THE EXPONENT IN HALF

Authors
LOU DC CHANG CC
Citation
Dc. Lou et Cc. Chang, FAST EXPONENTIATION METHOD OBTAINED BY FOLDING THE EXPONENT IN HALF, Electronics Letters, 32(11), 1996, pp. 984-985
Citations number
9
Categorie Soggetti
Engineering, Eletrical & Electronic
Journal title
Electronics Letters → ACNP
ISSN journal
00135194
Volume
32
Issue
11
Year of publication
1996
Pages
984 - 985
Database
ISI
SICI code
0013-5194(1996)32:11<984:FEMOBF>2.0.ZU;2-O
Abstract
On average, the square-and-multiply method requires 1.5k multiplicatio ns to evaluate x(E), where k is the bit length of E. Recently, Wu and Chang proposed an efficient method for computing x(E), which needs 156 k/128 multiplications. By folding the exponent E in half and combining Wu and Chang's method, we present a more efficient method for evaluat ing x(E). On average, our new method needs only 149k/128 + 3 multiplic ations.