Related Concepts
Definition
Right-to-left exponentiation methods read the exponent from the least significant bit (or other digit) up to the most significant one.
Background
Many exponentiation methods have two variants: one that examines exponents starting at the most significant digit and going down to the least significant one, that is, in left-to-right direction (assuming big-endian notation); and a related one that examines exponents in the opposite direction, that is, right-to-left. For specific methods, see the entries on binary exponentiation, 2k-ary exponentiation, and sliding window exponentiation.
Theory
There is a general duality between left-to-right and right-to-left exponentiation: this is explained by representing addition chains (fixed-exponent exponentiation) as directed multi-graphs such that reversing all arcs turns left-to-right exponentiation into right-to-left exponentiation, or the other way around [ 1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Knuth DE (1998) The art of computer programming, vol. 2: seminumerical algorithms, 3rd edn. Addison-Wesley, Reading, p 466, 639, 4.6.3–39
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer Science+Business Media, LLC
About this entry
Cite this entry
Möller, B. (2011). Right-to-Left Exponentiation. In: van Tilborg, H.C.A., Jajodia, S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-5906-5_43
Download citation
DOI: https://doi.org/10.1007/978-1-4419-5906-5_43
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4419-5905-8
Online ISBN: 978-1-4419-5906-5
eBook Packages: Computer ScienceReference Module Computer Science and Engineering