`powermod`

Modular exponentiation: the remainder of a power divided by a modulus.

Category: Symbolic Computations in MATLAB > Operators and Elementary Operations

Syntax

r = powermod(a, b, m)

Computes mod(a^b, m) without forming the full power.

Description

The result equals mod(a^b, m), but the power is reduced step by step by repeated squaring, so large exponents do not overflow. This is the basic operation behind modular arithmetic in number theory and in schemes such as RSA.

The arguments must be integers and the modulus positive; otherwise an error is raised. A negative exponent uses the modular inverse of the base, and the result is NaN when the base has no inverse. Array bases give an array of the same size.

Input arguments

a: Integer base, scalar or array.
b: Nonnegative integer exponent.
m: Positive integer modulus.

Output arguments

r: Remainder in the range 0 to m-1.

Example

Large powers modulo a number

powermod(2, 10, 1000)
powermod([2 3 5], 20, 7)
powermod(7, 128, 13)

Output

ans = 24
ans = 1×3

     4     2     4
ans = 3

Notes

In MatLivre powermod accepts numeric (double or integer type) arguments only; symbolic integers raise an error.

powermod