powermod

Modular exponentiation

Syntax

c = powermod(a,b,m)

Description

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

Examples

Compute Modular Exponentiation

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

c = powermod(3,5,7)

c =
     5

Prove Fermat's Little Theorem

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

Compute Fermat Primes Using Fermat Primality Test

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

a — Base

number | vector | matrix | array | symbolic number | symbolic array

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

b — Exponent or power

number | vector | matrix | array | symbolic number | symbolic array

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

m — Divisor

number | vector | matrix | array | symbolic number | symbolic array

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

More About

Modular Exponentiation

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

c = a^b 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.