Modular exponentiation

Modular exponentiation computes an integer power and reduces the result modulo a positive integer. It can be performed without constructing the potentially enormous ordinary power.

Repeated squaring: A method that computes powers by repeatedly squaring and combining selected powers. It reduces exponentiation to logarithmically many multiplications, with reduction modulo the modulus after each step.
Modular arithmetic: Arithmetic in which integers are identified when they have the same remainder modulo a fixed positive integer. Modular exponentiation is exponentiation performed within this arithmetic system.
RSA cryptosystem: A public-key cryptosystem whose encryption and decryption operations use exponentiation modulo a composite integer. RSA encrypts and decrypts messages by modular exponentiation with different exponents.
Modular multiplication: Multiplication followed by reduction modulo a positive integer. It is the basic repeated operation used to compute a modular power.
Binary exponentiation: An algorithm that computes a power by processing the binary digits of its exponent. Its bit-by-bit procedure is a standard implementation of modular exponentiation.
Congruence relation: A relation stating that two integers differ by a multiple of a specified integer. It gives the precise meaning of reducing a power modulo the modulus.
Diffie–Hellman key exchange: A protocol that lets two parties establish a shared secret using exponentiation in a finite group. Its classic form computes powers modulo a prime, relying on modular exponentiation's efficiency.
Modular division: Division in modular arithmetic, defined through multiplication by an inverse when that inverse exists. Unlike exponentiation, division is not always defined for a given divisor and modulus.
Square-and-multiply algorithm: An exponentiation algorithm that squares a running value and multiplies by the base when a selected exponent bit is set. It performs the modular products needed to build the result from exponent bits.
Residue class: The set of integers that have the same remainder modulo a fixed positive integer. Each intermediate result represents a residue class rather than an unrestricted integer.

Linked from 11 pages