Main Content

# powermod

Modular exponentiation

## 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.

## Version History

Introduced in R2018a