## Cryptography: Modular Arithmetic

Topics

- Extended Euclidean Algorithm
- Modular Arithmetic 🢀
- Diffie-Hellman Key Exchange
- Public Key Cryptography

### Introduction

In modular arithmetic, integer numbers "wrap around" upon reaching a certain value called the modulus. An example is in the 12-hour clock. If the time is 7:00 now, then 8 hours later it will be 3:00 because 7 + 8 = 15, 15 - 12 = 3.

### Congruence

Modular arithmetic is based on the congruence relation.
Two numbers `a` and `b` are congruent modulo `n`
if their difference `a − b` is an integer multiple of `n`.
This is written as

The arithmetic operations like addition and multiplication
are carried over to the respective congruences, e.g.

if

_{1}≡ b

_{1}(mod n).

_{2}≡ b

_{2}(mod n).

then

_{1}⋅ a

_{2}≡ b

_{1}⋅ b

_{2}(mod n)

_{1}≡ k ⋅ b

_{1}(mod n).

In general, we cannot cancel a common multiplicative factor from a congruence. For example, it is:

but after cancelling 2 we get:

However, if
`k` is coprime with `n`
then it can be cancelled:

implies

Eq. (2a) says that `n` divides
k ⋅ a - k ⋅ b = k ⋅ (a -b).
Since `n` and `k` have no common multiplicative factors,
`n` must divide `a - b`,
so eq. (2b) follows.

The following useful property will be applied in the public key cryptography. If

and `n` and `m` are coprime, then

The proof is easy but tricky. Equations (3) can be written as

_{1}⋅ n = k

_{2}⋅ m

for some integers `k _{1}` and

`k`. Because

_{2}`n`and

`m`are coprime we know from the Bézout's idententity that there exist numbers

`x`and

`y`such that

We multiply eq. (6) by `a - b`
and substitute the expressions (5):

_{2}⋅ m ⋅ n ⋅ x + k

_{1}⋅ n ⋅ m ⋅ y

_{2}⋅ x + k

_{1}⋅ y) ⋅ (m ⋅ n)

So, `a - b` is a multiple of `n · m`
and the eq. (4) follows.

### Integers modulo `n`

When we compute `(mod n)`
it is sufficient to consider only the numbers `0, 1, .. n-1`
because all other numbers are reduced to them via the congruence relation.
The set of these "residues" **Z**_{n} is
a mathematical structure called a ring.
A ring provides the operations of addition and multiplication
with the usual properties. It does not provide division.
However, in the special case when `n = prime p` each number `a`
in **Z ^{+}**

_{p}=

`{1, .. p-1}`has also an inverse with respect to multiplication that is denoted

`a`

^{-1}^{-1}≡ 1 (mod p) for a ≢ 0 (mod p)

because `gcd(a, p) = 1`.
The inverse `a ^{-1}` can be computed using the Extended Euclidean Algorithm.
So, the set

**Z**

_{p}provides also division and is a mathematical field, denoted by

**F**

_{p}or

**GF**(p) (GF for Galois Field).

### Fermat's Little Theorem

If `p` is a prime number and `a` is a natural number,
`a ≢ 0 (mod p)`, then

^{p-1}≡ 1 (mod p).

Proof: consider the numbers

all `(mod p)`. These numbers are different because if it were

_{1}⋅ a = k

_{2}⋅ a (mod p)

we could cancel `a` since
`a` and `p` are coprime and get

_{1}= k

_{2}

So, these `p-1` numbers
correspond to the numbers

in some order. Consequently the product of the numbers (9) equals the product of the numbers (10):

^{p-1}⋅ (p-1)! ≡ 1 ⋅ (p-1)! (mod p)

Now we may cancel `(p-1)!` in **GF**(p) and get equation (8).

A simple corollary from equation (8) is:

^{p}≡ a (mod p) for every a

### Euler's Φ Function

Euler's generalization of Fermat's Little Theorem is that
for any modulus `n`

^{Φ(n)}≡ 1 (mod n)

provided that `a` and `n` are relatively prime.
Here, `Φ(n)` is the count of numbers `0, 1, .. n-1`
that are relatively prime to `n`.
The proof is analogous to the proof of the Fermat's theorem.
Notice that the Fermat's theorem is a special case
of the Euler's theorem, because `Φ(p) = p - 1`
for a prime `p`.

The Euler's Φ function satisfies the following relation
for coprime `m` and `n` (without proof):