powermod

Modular power of number

Syntax

powermod(a,b,m)

Description

example

powermod(a,b,m) returns the modular power ab mod m. Use powermod to compute the modular power without calculating ab.

Examples

collapse all

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

Compute mod(3^5,7).

powermod(3,5,7)
ans =
     5

Fermat's little theorem states that where p is prime and a is not divisible by p, 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;
powermod(a,p-1,p)
ans =
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;
powermod(a,p-1,p)
ans =
     1     1     1     1

Fermat's little theorem states that where p is prime and a is not divisible by p, a(p–1) mod p is 1. Test numbers from 300 to 400 for primality by using Fermat's little theorem with base 2. Find Fermat pseudoprimes by comparing results with isprime.

Test numbers from 300 to 400 for primality.

N = 300:400;
remainder = powermod(2,N-1,N);
primesFermat = N(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 with isprime. 341 is a Fermat pseudoprime.

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

Input Arguments

collapse all

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

Input, specified as a number, vector, matrix, array, or a symbolic number or array. b must be a nonnegative integer.

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

Introduced in R2018a