Number theory

Cryptography

Fundamentals

Number theory

This section is currently under construction. Use the search bar to find the topic you are looking for.

Number theory basics

Notations

$a \mid b$ - $a$ divides $b$
$a \Z$ - the set of all integers that are multiples of $a$

Divisibility

GCD - Greatest Common Divisor

The greatest common divisor of two integers $a$ and $b$ is the largest integer that divides both $a$ and $b$ :

a \Z + b \Z = \gcd(a, b) \Z

This can be extended to more than two integers. When $\gcd(a, b) = 1$ , we say that $a$ and $b$ are coprime.

We also have the following properties:
$\gcd(a, b) = \gcd(b, a)$
$\gcd(a, b) = \gcd(-a, b) = \gcd(a, -b) = \gcd(-a, -b)$
$\gcd(a, b) = \gcd(a, b - a)$
$\gcd(a, b) = \gcd(a, b \mod a)$
$\gcd(k \cdot a, k \cdot b) = k \cdot \gcd(a, b)$

Bezout's identity

For any $a_1, a_2 \cdots a_n \in \Z$ , they are coprime if and only if there exist integers $x_1, x_2 \cdots x_n$ such that:

x_1 \cdot a_1 + x_2 \cdot a_2 + \cdots + x_n \cdot a_n = 1

Gauss's lemma

a \mid bc

and

\gcd(a, b) = 1

, then

a \mid c

LCM - Least Common Multiple

The least common multiple of two integers $a$ and $b$ is the smallest integer that is a multiple of both $a$ and $b$ :

a \Z \cap b \Z = \text{lcm}(a, b) \Z

This can be extended to more than two integers. We also have the following properties: $\text{lcm}(a, b) = \text{lcm}(b, a)$
$\text{lcm}(a, b) = \text{lcm}(-a, b) = \text{lcm}(a, -b) = \text{lcm}(-a, -b)$
$\text{lcm}(a, b) = \text{lcm}(a, b - a)$
$\text{lcm}(a, b) = \text{lcm}(a, b \mod a)$
$\text{lcm}(k \cdot a, k \cdot b) = k \cdot \text{lcm}(a, b)$
$\text{lcm}(a, b) \cdot \gcd(a, b) = \mid a \cdot b \mid$

Prime numbers

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Fundamental theorem of arithmetic

Every integer greater than 1 can be expressed uniquely as a product of prime numbers.

n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}

Fermat's little theorem

If $p$ is a prime number and $a$ is an integer not divisible by $p$ , then:

a^{p-1} \equiv 1 \mod p

Wilson's theorem

A natural number $p$ is a prime number if and only if:

(p-1)! \equiv -1 \mod p

Euler’s totient function

Euler's totient function

The Euler’s totient function $\phi(n)$ is the number of positive integers less than $n$ that are coprime to $n$ .

\phi(n) = \mid \lbrace k \in \N \mid 1 \leq k < n, \gcd(k, n) = 1 \rbrace \mid

Euler's totient function properties

If $p$ is a prime number, then $\phi(p) = p - 1$
If $a$ and $b$ are coprime, then $\phi(a \cdot b) = \phi(a) \cdot \phi(b)$
If $p$ is a prime number and $k \in \N$ , then $\phi(p^k) = p^k - p^{k-1}$

Euler's theorem

If $a$ and $n$ are coprime, then:

a^{\phi(n)} \equiv 1 \mod n

Tricks

Recovering a base from two coprime powers with Bézout
If you can obtain two powers $g^{e_1}$ and $g^{e_2}$ of the same unknown base $g$ with coprime exponents ( $\gcd(e_1, e_2) = 1$ ), you can recover $g$ itself even without being able to invert the exponentiation (no root, no discrete log needed). Bézout’s identity gives integers $u, v$ such that $u e_1 + v e_2 = 1$ , hence:
$g = g^{u e_1 + v e_2} = (g^{e_1})^u \cdot (g^{e_2})^v$
This works in any group (integers mod $n$ , matrices, elliptic curve points), and is typical against an oracle that exponentiates a chosen base by a secret (but coprime between calls) exponent. The exponents $u, v$ come from the extended Euclidean algorithm (xgcd in SageMath).