Concept

Exponentiation by squaring

Summary
In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add. Basic method Recursive version The method is based on the observation that, for any integer n > 0, one has: x^n= \begin{cases} x , ( x^{2})^{(n - 1)/2}, & \mbox{if } n \mbox{ is odd} \ (x^{2})^{n/2} , & \mbox{if } n \mbox{ is even} \end{cases} If the exponent is zero then the answer is 1 and if the e
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading