> For the complete documentation index, see [llms.txt](https://www.ctfrecipes.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.ctfrecipes.com/cryptography/general-knowledge/maths/modular-arithmetic/fermats-little-theorem.md).

# Fermat's little theorem

{% hint style="info" %}
This page is about modular arithmetic.\
\
The integers modulo `p` define a field, denoted `Fp`.\\

A finite field `Fp` is the set of integers `{0,1,...,p-1}`, and under both addition and multiplication there is an inverse element `b` for every element `a` in the set, such that\
`a + b = 0` and `a * b = 1`.
{% endhint %}

Fermat's Little Theorem is a result in number theory that states that if \*\*`a` \*\* is an integer and **`p`** is a prime number, then for all integers **`a`**:

$$
a^{p-1} \equiv 1 \bmod p
$$

This means that :

$$
\frac{a^{p-1}-1}{p}=0
$$

In cryptography, it is used in the modular exponentiation algorithm, which is a basic building block in many public key encryption algorithms such as the RSA algorithm.

## Modular inversion

**Modular inversion**, also known as **modular reciprocal**, is the process of finding the multiplicative inverse of an integer **`a`** modulo **`p`**.

The multiplicative inverse of **`a`** modulo **`p`** is an integer **`b`** such that :

$$
a \* b \equiv 1 \bmod p
$$

{% hint style="info" %}
**`b`** and is unique for each **`a`** and **`m`** couple
{% endhint %}

There is two methods in order to calculate the modular inverse of a number

### Using extended Euclid's algorithm

The [extended euclid's algorithm](/cryptography/general-knowledge/maths/modular-arithmetic/greatest-common-divisor.md#extended-euclids-algorithm) permit to quickly find the modular inverse such as :

$$
a^{-1} = u \bmod p
$$

Where `u` is solution for :

$$
a*u+p*v = 1
$$

{% hint style="info" %}
This equation is solved using the extended Euclid's algorithm.\
Exemple with `a = 3 and p = 13`

```python
a = 3, p = 13
gcd, u, v = egcd(a,p)
# 3 * -4 + 13 * 1 = 1
x = u % p
# 9 = -4 % 13
assert(a * x % p == 1 % p)
```

{% endhint %}

### Continuing the Fermat's little theorem

The theorem says :

$$
a^{p-1} \equiv 1 \bmod p \iff a^{p-1} \bmod p = 1
$$

The equation can be continued :

$$
a^{p-1} \equiv 1 \bmod p \ a^{p-1} \* a^{-1} \equiv a^{-1} \bmod p \ a^{p-2} \* a \* a^{-1} \equiv a^{-1} \bmod p \ a^{p-2} \equiv a^{-1} \bmod p \iff a^{p-2} \bmod p = a^{-1}
$$

{% hint style="info" %}
Using the same example as before :

```python
# 3 * x ≡ 1 mod 13
a = 3
p = 13
# x = a^(p-2) % p
# x = 3^(13-2) % 13
x = pow(a, p-2, p)
# x = 9
assert(a * x % p == 1 % p)
```

{% endhint %}

## Resource

{% embed url="<https://en.wikipedia.org/wiki/Fermat>" %}