powermod

Modular exponentiation

collapse all in page

Syntax

c = powermod(a,b,m)

Description

example

c = powermod(a,b,m) returns the modular exponentiation ab mod m. The input a,b must be integers, and m must be a nonnegative integer. For more information, see Modular Exponentiation.

Examples

collapse all

Compute the modular exponentiation ab mod m by using powermod. The powermod function is efficient because it does not calculate the exponential ab.

c = powermod(3,5,7)
c =
     5

Fermat's little theorem states that if p is prime and a is not divisible by p, then a(p–1) mod p is 1.

Test Fermat's little theorem for p = 5, a = 3. As expected, powermod returns 1.

p = 5;
a = 3;
c = powermod(a,p-1,p)
c =
1

Test the same case for all values of a less than p. The function powermod acts element-wise to return a vector of ones.

p = 5;
a = 1:p-1;
c = powermod(a,p-1,p)
c =
     1     1     1     1

Fermat's little theorem states that if p is a prime number and a is not divisible by p, then a(p–1) mod p is 1. On the contrary, if a(p–1) mod p is 1 and a is not divisible by p, then p is not always a prime number (p can be a pseudoprime).

Test numbers from 300 to 400 for primality by using Fermat's little theorem with base 2.

p = 300:400;
remainder = powermod(2,p-1,p);
primesFermat = p(remainder == 1)
primesFermat =
   307   311   313   317   331   337   341   347   349   353...
   359   367   373   379   383   389   397

Find Fermat pseudoprimes by comparing the results with isprime. 341 is a Fermat pseudoprime.

primeNumbers = p(isprime(p));
setdiff(primesFermat,primeNumbers)
ans =
   341

Input Arguments

collapse all

Base, specified as a number, vector, matrix, array, or a symbolic number or array. a must be an integer.

Exponent or power, specified as a number, vector, matrix, array, or a symbolic number or array. b must be an integer.

Divisor, specified as a number, vector, matrix, array, or a symbolic number or array. m must be a nonnegative integer.

More About

collapse all

Modular Exponentiation

For a positive exponent b, the modular exponentiation c is defined as

c = ab mod m.

For a negative exponent b, the definition can be extended by finding the modular multiplicative inverse d of a modulo m, that is

c = d ‒b mod m.

where d satisfies the relation

ad mod m = 1.

See Also

| | |

Introduced in R2018a

Symbolic Math Toolbox Documentation

Support