There are many situations where an exponentiation of a fixed base element \(g \in G\), with G being some group, by an arbitrary positive integer exponent e is performed. For instance, such cases occur at the Diffie–Hellman key agreement. Fixed-base exponentiation aims to decrease the number of multiplications compared to general exponentiation algorithms such as the binary exponentiation algorithm. With a fixed base, precomputation can be done once and then used for many exponentiations. Thus the time for the precomputation phase is virtually irrelevant. Using precomputations with a fixed base was first introduced by Brickell et al. (and thus it is also referred to as the BGMW method) [1]. In the basic version, values \(g_0=g\), \(g_1=g^2, g_2=g^{2^2},\ldots, g_t=g^{2^t}\) are precomputed, and then the binary exponentiation algorithm is used without performing any squarings. Having an exponent e of bit-length \(n+1\), such a strategy requires on average \(n/2\)multiplications whereas...
This is a preview of subscription content, log in via an institution to check access.
References
Brickell, E.F., D.M. Gordon, K.S. McCurley, and D.B. Wilson (1992). “Fast exponentiation with precomputations.” Advances in Cryptology—EUROCRYPT'92, Lecture Notes in Computer Science, vol. 658, ed. R.A. Rueppel. Springer-Verlag, Berlin.
de Rooij, P. (1994). “Efficient exponentiation using precomputation and vector addition chains.” Advances in Cryptology—EUROCRYPT'94, Lecture Notes in Computer Science, vol. 950, ed. A. De Santis. Springer-Verlag, Berlin.
Gordon, D.M. (1998). “A survey of fast exponentiation methods.” J. Algorithms, 27, 129–146.
Hankerson, D., J.L. Hernandez, and A. Menezes (2000). “Software implementation of elliptic curve cryptography over binary fields.” Proceedings of Cryptographic Hardware and Embedded Systems, CHES 2000, Lecture Notes in Computer Science, vol. 1965, eds. Ç.K. Koç and C. Paar. Springer-Verlag, Berlin.
Lim, C. and P. Lee (1994). “More flexible exponentiation with precomputation.” Advances in Cryptology—CRYPTO'94, Lecture Notes in Computer Science, vol. 839, ed. Y.G. Desmedt. Springer-Verlag, Berlin.
Menezes, A.J., P.C. van Oorschot, and S.A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. Boca Raton, FL.
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 International Federation for Information Processing
About this entry
Cite this entry
Weimerskirch, A. (2005). Fixed-Base Exponentiation. In: van Tilborg, H.C.A. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA . https://doi.org/10.1007/0-387-23483-7_170
Download citation
DOI: https://doi.org/10.1007/0-387-23483-7_170
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-23473-1
Online ISBN: 978-0-387-23483-0
eBook Packages: Computer ScienceReference Module Computer Science and Engineering