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

Official source

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

Related publications

Related people

No results

No results

Related units

Related concepts

No results

No results

Related courses

No results

Related lectures

No results