Exponentiation by squaring

<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a> and <a href="/facts/Computer_programming/QmSsFnu0">computer programming</a>, exponentiating by squaring is a general method for fast computation of large <a href="/facts/Positive_integer/u65og8JE">positive integer</a> powers of a <a href="/facts/Number/auQSAE2m">number</a>, or more generally of an element of a <a href="/facts/Semigroup/rgSdk2kt">semigroup</a>, like a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> or a <a href="/facts/Square_matrix/5TP9mNNn">square matrix</a>. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in <a href="/facts/Modular_arithmetic/0wtRa5dU">modular arithmetic</a> or powering of matrices. For semigroups for which <a href="/facts/Abelian_group/FfWwmx4R">additive notation</a> is commonly used, like <a href="/facts/Elliptic_curve/60jvaHSA">elliptic curves</a> used in <a href="/facts/Cryptography/e94PEVau">cryptography</a>, this method is also referred to as double-and-add.
</p>

Exponentiation by squaring open-in-new

Exponentiation by squaring