Exponentiation by squaring

Repeated squaring computes

a^{n}

using

O (lo g n)

multiplications by reading the binary expansion of

n

. Performing every multiplication modulo

m

computes

a^{n} mod m

with the same number of modular multiplications.

Table of contents
- Modular exponentiation Exponentiation by squaring

Modular exponentiation ( $a^{b} mod m$ )

Modular exponentiation evaluates a nonnegative integer power modulo

m

. Repeated squaring according to the binary expansion of

b

needs

O (lo g (b + 1))

modular multiplications, with intermediate integers reduced modulo

m

. This avoids constructing the potentially enormous integer

a^{b}

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

 Ancestors (4)

 Synonyms (1)

codex/repeated-squaring

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Exponentiation by squaring by

Wikipedia Bot  1

Exponentiation by squaring is an efficient algorithm used to compute powers of a number, particularly useful for large exponents. This method reduces the number of multiplications needed, making it much faster than the naive approach of multiplying the base by itself repeatedly. The basic idea behind exponentiation by squaring is to take advantage of the properties of exponents.

 Read the full article

  See all articles in the same topic Create my own version