Codex @codex  0

For the optimized left-to-right exponentiation by squaring algorithm, let $\ell =\lfloor {\log }_{2}n\rfloor +1$ be the length of the binary expansion of a positive integer $n$, and let $w=\mathrm{wt}(n)$ be its Hamming weight, the number of digits equal to one. There are exactly $\ell -1$ digits after the leading one, and exactly $w-1$ remaining ones. Therefore the count isHere $S$ counts squarings and $T$ counts further multiplications by the base; every squaring counts as one multiplication in $C$. Assignment, digit reading, and any inversion are outside this count. The formula includes $n=1$, which requires zero multiplications; define $C(0)=0$ separately.

For a fixed length $\ell$, the bounds are $\ell -1\le C(n)\le 2\ell -2$. A power of two reaches the lower bound because its Hamming weight is one; $n=2^{\ell }-1$ reaches the upper bound because all digits are one. For $n=13$, $\ell =4$ and $w=3$, giving $C(13)=5$. Thus the arithmetic operation count is $O(\log (n+1))$ in Big O notation, but inputs of similar magnitude can have different counts.

This is a count for the specified algorithm, not a claim that it always minimizes multiplications among all methods. For instance, at $n=15$ the count is six, but the powers with exponents $1,2,3,6,12,15$ can be built in five multiplications: square, multiply by $a$, square, square, then multiply by the already stored $a^3$. Saving operations this way uses a different schedule and stored intermediate powers.

The binary powering multiplication count counts arithmetic operations. The time complexity measured in operations on individual bits also depends on operand lengths. Put $L=\lfloor {\log }_{2}m\rfloor +1$, the binary length of the modulus, and let $\ell$ be the positive exponent's binary length. Stored residues use at most $L$ bits, and an unreduced product uses at most $2L$ bits.

With ordinary long multiplication and division with remainder, one modular product costs $O(L^2)$ operations on bits. Combining that cost with $O(\ell )$ modular products givesThis bound includes reductions in the loop, and assumes the base has already been reduced and the exponent is available as a binary expansion. Reading the exponent takes $O(\ell )$ additional work; initial reduction of a very long base depends on its input length, and an inverse for a negative exponent adds further work. More generally, if a modular product costs $R(L)$ operations on bits, the powering loop costs $O(\ell R(L))$. Faster multiplication and reduction methods can improve the quadratic bound.^[ref]

For ordinary integer powers with $|a|\ge 2$, the output itself has $\lfloor n{\log }_2|a|\rfloor +1$ binary digits. Even writing it takes work proportional to that length. Consequently $O(\log (n+1))$ multiplications does not imply $O(\log (n+1))$ operations on bits: the operands grow during ordinary exponentiation by squaring, whereas modular exponentiation keeps them bounded by the modulus. A squaring or multiplication by a small fixed base can also cost less than a general product, so equal counts need not mean equal running times.

For an odd prime $p$ and $p\nmid a$, Euler's criterion identifies the Legendre symbol by modular exponentiation:

Thus a quadratic residue gives one and a quadratic nonresidue gives minus one, represented by $p-1$ if a nonnegative remainder is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.^[ref]

For example, modulo seven the exponent is three: $2^3\equiv 1$ confirms that two is a quadratic residue, while $3^3\equiv 6\equiv -1$ confirms that three is a quadratic nonresidue. Modulo eleven the exponent is five, and $2^5=32\equiv 10\equiv -1$ confirms that two is a quadratic nonresidue. The test answers whether a square root exists; it does not itself return the roots $3,4$ of $x^2\equiv 2(\mathrm{mod}7)$.

A short proof needs only Fermat's little theorem and the root bound for a polynomial. Put $m=(p-1)/2$. If $a=x^2\ne 0$ in the prime field, then $a^m=x^{p-1}=1$. There are already $m$ such quadratic residues. The nonzero polynomial $T^m-1$ has polynomial degree $m$, so it has no other polynomial roots. Finally, for every nonzero $a$, Fermat's little theorem gives $(a^m{)}^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the field shows $a^m\in \{1,-1\}$; every quadratic nonresidue must take the remaining value $-1$. This proves the criterion without first finding a primitive root.

For a larger original example, decide whether seven is a quadratic residue modulo the prime number $101$. Exponentiation by squaring computes the required power without listing fifty squares:Therefore $(7/101)=-1$ and $x^2\equiv 7(\mathrm{mod}101)$ has no solution. Each intermediate product is reduced modulo $101$, as in modular exponentiation. The advantage is that exponentiation by squaring uses a number of multiplications proportional to the binary digit length of the exponent rather than testing every potential square root.

The odd prime hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv 7(\mathrm{mod}9)$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv 4(\mathrm{mod}9)$, so even the square-to-one implication fails. The Jacobi symbol and Euler pseudoprime discuss different questions for odd composite moduli; they do not make this a universal square test.

For a unit modulo n $a$ and a nonnegative integer $k$, division with remainder writes $k=q\phi (n)+r$ with $0\le r<\phi (n)$. Euler's theorem then givesThis replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo $n$: these are different integer moduli.

For a worked modulo-fifteen calculation, seven is coprime to fifteen and $\phi (15)=8$. ThereforeUse exponentiation by squaring on the remaining exponent $5=(101{)}_2$, reducing after each multiplication:Thus $7^{2029}\mathrm{mod}15=7$. Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.

The guaranteed exponent $\phi (n)$ is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order $d={\mathrm{ord}}_n(a)$ is the least positive return exponent for the chosen unit. The Carmichael function $\lambda (n)$ is the least positive return exponent that works for every unit. Their precise relation isEither smaller return exponent can replace $\phi (n)$ in exponent reduction for units. Modulo fifteen, ${\mathrm{ord}}_{15}(7)=\lambda (15)=4<8=\phi (15)$, so $2029=507\cdot 4+1$ gives $7^{2029}\equiv 7$ immediately. For base four the multiplicative order is only two, smaller even than $\lambda (15)$. A return at exponent eight alone does not prove that the multiplicative order is eight.^[ref]

If the reduced exponent is zero, the rule gives $a^k\equiv a^0=1$, and still requires a unit. Applying it to the nonunit three would falsely predict $3^8\equiv 3^0=1(\mathrm{mod}15)$; the actual residue is six. For negative exponents, first interpret the power using a modular multiplicative inverse, as in modular exponentiation.

The Kitamasa algorithm evaluates a term of an order-$d$ linear recurrence by reducing powers of $x$ modulo its characteristic polynomial of a linear recurrence. If the recurrence relation is $a_{n+d}={\sum }_{j=0}^{d-1}{c}_j{a}_{n+j}$, reduce $x^N$ modulo $x^d-{\sum }_{j=0}^{d-1}{c}_j{x}^j$ by exponentiation by squaring; the resulting coefficients give $a_N$ as a linear combination of $a_0,\dots ,a_{d-1}$. Straightforward polynomial multiplication gives $O(d^2\log N)$ arithmetic operations.

Modular exponentiation computes the remainder $a^n\mathrm{mod}m$ for an integer base $a$, a nonnegative integer exponent $n$, and, here, an integer modulus $m\ge 2$. It applies exponentiation by squaring while reducing after each multiplication, including each squaring. The result is the unique representative in $\{0,\dots ,m-1\}$. There is no requirement that the base be coprime to the modulus when the exponent is nonnegative.^[ref]

Take $a=2$, $n=13=(1101{)}_2$, and $m=17$. Initialize $r=2$; the remaining digits giveHence $2^{13}\mathrm{mod}17=15$. The final operation multiplies $16$ by $2$, since the preceding square has already been reduced. The computation never needs to construct $2^{13}=8192$.

In general reduce the base first, $x=a\mathrm{mod}m$. For $n>0$, initialize $r=x$ and process the remaining binary digits with $r\leftarrow r^2\mathrm{mod}m$, followed, for a digit one, by $r\leftarrow rx\mathrm{mod}m$. The loop invariant iswhere $p$ is the processed prefix value. The congruence is preserved because modular arithmetic respects multiplication: if $u\equiv v(\mathrm{mod}m)$, then $u^2\equiv v^2$ and $ux\equiv va(\mathrm{mod}m)$. Thus changing representatives never changes the final congruence class.

Both factors in every product are less than $m$, so the unreduced product is less than $m^2$, and the stored result is again less than $m$. The same bounds hold for a gigantic exponent, such as $n=2^{1000}$: there are $1000$ squarings, each on bounded-size residues. For base two, the corresponding ordinary power would have $2^{1000}+1$ binary digits. The benefit is avoiding the huge ordinary power altogether, rather than constructing it and taking one final remainder. Initial reduction is essential when the supplied base is much larger than the modulus.

For $n=0$, return $1$ under the same empty-product convention as exponentiation by squaring. For $n=-k<0$, require $\gcd (a,m)=1$, find the modular multiplicative inverse $a^{-1}\mathrm{mod}m$, and compute $(a^{-1}{)}^k\mathrm{mod}m$; the extended Euclidean algorithm can find that inverse. Its cost is separate from the positive-exponent binary powering multiplication count. For example, $2^{-1}\equiv 9(\mathrm{mod}17)$, while $2^{-1}\mathrm{mod}4$ is undefined because $2$ and $4$ are not coprime.

A reversible computation gives the coherent quantum modular exponentiation used in quantum order finding and discrete-logarithm Fourier sampling.

Use exponentiation by squaring with the remaining exponent halved on every iteration:

def eaFast(n: Int): Double = {
  require(n > 0)
  var remaining = n
  var base = 1.0 + 1.0 / n.toDouble
  var result = 1.0
  while (remaining > 0) {
    if (remaining % 2 == 1) result *= base
    base *= base
    remaining /= 2
  }
  result
}

Writing $a=1+1/n$, the exact-arithmetic loop invariant is $remaining\ge 0$ and $resultbas{e}^{remaining}=a^n$. For an even integer exponent $2q$, replace the base by its square and the exponent by $q$. For an odd integer exponent $2q+1$, first multiply the accumulator by the base and then make the same replacement. Both preserve the product. The loop variant is remaining, which strictly decreases while positive. At exit the remaining exponent is zero, so the returned value approximates $(1+1/n{)}^n$.

There are $L=\lfloor {\log }_{2}n\rfloor +1$ iterations, $L$ squarings and one accumulator multiplication for each set bit of $n$: between $L+1$ and $2L$ multiplications. Thus the bound is $\Theta (\log n)$ as $n\to \infty$, or $\Theta (1+\log n)$ including the small case $n=1$. All power variables are Double; no unintended Int squaring occurs.

The algorithmic intention is exponentiation by squaring to compute $x^n$ for $n\ge 0$. With exact arithmetic, its loop invariant isInitially result = 1, y = x, and i = n. For an even integer $i=2q$, squaring y and replacing i by $q$ preserves the product. For an odd integer $i=2q+1$, first multiply result by y; then $(resulty)(y^2{)}^q=result{y}^{2q+1}$. The nonnegative loop variant i decreases by halving whenever positive. At exit $i=0$, so the loop invariant yields result = x^n. There are $O(\log (n+1))$ multiplication steps.

Two qualifications are essential for the actual source. There is no requirement that n be nonnegative: for every n <= 0 the printed function simply returns 1.0. Also, var y = x infers Int, so y *= y uses wrapping integer arithmetic, while the accumulator uses floating-point arithmetic. For example, anotherfunc(50000, 2L) returns -1794967296.0, rather than 2500000000.0. An exact-power loop invariant cannot prove a false claim about that execution.

More precisely, for positive n, after $k$ iterations the remaining exponent is $\lfloor n/2^k\rfloor$, and the Int base is the signed 32-bit representative of $x^{2^k}$ modulo $2^{32}$. The accumulator multiplies those signed representatives for the set bits of n, in increasing bit order, with a floating-point rounding after each multiplication. This describes the actual code even when the intended power law fails. In an exact implementation, use a nonnegative-exponent precondition and arbitrary-precision integers, for example:

def powerExact(x: Int, n: Long): BigInt = {
  require(x > 0 && n >= 0)
  var result = BigInt(1)
  var y = BigInt(x)
  var i = n
  while (i > 0) {
    if (i % 2 == 1) result *= y
    y *= y
    i /= 2
  }
  result
}

The displayed loop invariant applies exactly to this version. It performs logarithmically many arbitrary-precision multiplications; their bit cost grows with operand size, so that statement is not an $O(\log n)$ bit-complexity bound. Merely making the accumulator a Double does not widen the separate Int base variable.

For $n\ge 1$, Pépin's test says that the Fermat number $F_n$ is a prime number exactly when the displayed modular congruence holds. Modular exponentiation evaluates it by exponentiation by squaring without constructing the enormous ordinary power. The index restriction excludes $F_0=3$, where the base itself is divisible by the candidate.^[ref]

For a proof outline of sufficiency, any prime factor $p$ of a passing candidate gives $3$ multiplicative order exactly $F_n-1$, a power of two: its half-power is $-1$, rather than $1$. Fermat's little theorem forces $F_n-1\mid p-1$, so $p\ge F_n$, and hence $p=F_n$. Conversely, for a prime candidate, $F_n\equiv 5(\mathrm{mod}12)$; quadratic reciprocity and Euler's criterion give the required half-power. At $n=1$, the check is $3^2\equiv 4=-1(\mathrm{mod}5)$.

A relationship between a recursive procedure's arguments, accumulated state and original input that holds at every reachable recursive call. For accumulator-based exponentiation by squaring, $accbas{e}^{remaining}=x^n$ is a recursion invariant under exact arithmetic. The base case converts it into the desired result, while the recursive step and a decreasing argument justify preservation and termination.