A Survey of Fast Exponentiation Methods

By Daniel M. Gordon. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Elliptic Curve Digital Signature Algorithm (ECDSA) (2001, unknown): “Input A public key Q xQ yQ associated with valid domain parameters q FR a b G n h Output Acceptance or rejection of the validity of Q Check that Q O Check that xQ and yQ are properly represented elements of Fq i e integers in the interval p in the case q p and bit strings of length m bits in the cas”
Efficient Arithmetic on Koblitz Curves (2000, methodology): “Moreover, NAF(n) has the fewest nonzero coefficients of any signed binary expansion of n [4].”
The Montgomery Powering Ladder (2002, methodology): “We restrict our attention to constrained environments and do not consider more sophisticated exponentiation algorithms (see [7] for a survey).”
A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography (2004, background): “With these primitives is point multiplication also possible [32].”
Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity (2004, methodology): “To ease the presentation, we assume that this is carried out with the (additive version of the) square-and-multiply algorithm. Other methods are discussed in [ 14 ].”
Order computations in generic groups (2007, methodology): “There are several generic fixed-base multi-exponentiation algorithms [73, 51, 13] which can compute w exponentiations of a common base using O ( n + w n lg n ) group operations (including any precomputation).”
Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms (2001, methodology): “Numerous methods for speeding up exponentiation and point multiplication have been discussed in the literature; for a survey, see [11,12,17].”
The Weil Pairing, and Its Efficient Calculation (2004, methodology): “We can use any of the fast exponentiation methods (see [8]) to calculate this value (with some care), and also use (9) sometimes to speed things up further.”
FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack (2014, unknown): “3 use the square-andmultiply exponentiation algorithm [28].”
The advantages of elliptic curve cryptography for wireless security (2004, methodology): “More sophisticated and efficient versions of the binary method have been developed (e.g., [ 10 ]).”