Unit 6 - Notes

MTH401

Unit 6: Number theory and its application in cryptography

1. Divisibility and Modular Arithmetic

Divisibility

Let $a$ and $b$ be integers with $a \neq 0$ . We say that $a$ divides $b$ (denoted $a \mid b$ ) if there exists an integer $k$ such that $b = ak$ .

If $a \mid b$ , then $a$ is a factor of $b$ , and $b$ is a multiple of $a$ .
If $a$ does not divide $b$ , we write $a \nmid b$ .

Properties of Divisibility:
For all integers $a, b, c$ :

Reflexive: $a \mid a$ .
Transitive: If $a \mid b$ and $b \mid c$ , then $a \mid c$ .
Linear Combination: If $a \mid b$ and $a \mid c$ , then $a \mid (mb + nc)$ for any integers $m, n$ .

Modular Arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus.

Congruence Definition:
Let $m$ be a positive integer. Two integers $a$ and $b$ are said to be congruent modulo $m$ if $m$ divides their difference ( $m \mid (a - b)$ ).
This is denoted as:

a \equiv b \pmod{m}

Equivalent Statements:

$a - b = km$ for some integer $k$ .
$a$ and $b$ have the same remainder when divided by $m$ .
$a = b + km$ .

Properties of Congruence:
If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$ , then:

$a + c \equiv b + d \pmod{m}$
$a - c \equiv b - d \pmod{m}$
$ac \equiv bd \pmod{m}$
$a^k \equiv b^k \pmod{m}$ for any positive integer $k$ .

2. Primes

Definition

A positive integer $p > 1$ is called prime if its only positive divisors are $1$ and $p$ .
A positive integer greater than $1$ that is not prime is called composite.

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written uniquely as a product of primes, up to the order of the factors.

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

Where

p_i

are distinct primes and

e_i \geq 1

3. GCD, LCM, and Euclidean Algorithm

Greatest Common Divisor (GCD)

The greatest common divisor of two integers $a$ and $b$ (not both zero), denoted $\gcd(a, b)$ , is the largest integer $d$ such that $d \mid a$ and $d \mid b$ .

If $\gcd(a, b) = 1$ , then $a$ and $b$ are relatively prime (or coprime).

Least Common Multiple (LCM)

The least common multiple of two integers $a$ and $b$ , denoted $\text{lcm}(a, b)$ , is the smallest positive integer that is divisible by both $a$ and $b$ .

Relationship between GCD and LCM:

a \cdot b = \gcd(a, b) \cdot \text{lcm}(a, b)

The Euclidean Algorithm

An efficient method for computing the GCD without factoring the numbers. It relies on the property: $\gcd(a, b) = \gcd(b, a \pmod{b})$ .

Procedure:
To find $\gcd(a, b)$ where $a > b$ :

Divide $a$ by $b$ to find remainder $r$ : $a = bq + r$ .
$\gcd(a, b) = \gcd(b, r)$ .
Repeat until the remainder is $0$. The last non-zero remainder is the GCD.

Example: Find $\gcd(252, 105)$ .

$252 = 2(105) + 42$
$105 = 2(42) + 21$
$42 = 2(21) + 0$
Since the remainder is 0, the previous remainder is the answer.
$\gcd(252, 105) = 21$ .

Bezout's Lemma

If $a$ and $b$ are positive integers, then there exist integers $x$ and $y$ such that:

ax + by = \gcd(a, b)

These integers

x

and

y

can be found using the Extended Euclidean Algorithm by working backward through the Euclidean Algorithm steps.

4. Linear Congruence and Inverses

Linear Congruence

A linear congruence is an equation of the form:

ax \equiv b \pmod{m}

where

x

is an unknown integer.

Solvability Condition:
The congruence has a solution if and only if $d \mid b$ , where $d = \gcd(a, m)$ .

If $d \nmid b$ , there are no solutions.
If $d \mid b$ , there are exactly $d$ incongruent solutions modulo $m$ .

Inverse of $a$ modulo $m$

The modular multiplicative inverse of $a$ modulo $m$ is an integer $\bar{a}$ (or $a^{-1}$ ) such that:

a \cdot \bar{a} \equiv 1 \pmod{m}

Existence: The inverse exists if and only if $\gcd(a, m) = 1$ (i.e., $a$ and $m$ are coprime).

How to find it: Use the Extended Euclidean Algorithm to find $x$ and $y$ such that $ax + my = 1$ . Then $x$ is the inverse of $a$ modulo $m$ .

Chinese Remainder Theorem (CRT)

CRT allows solving a system of simultaneous congruences with pairwise coprime moduli.

Theorem:
Let $m_1, m_2, \dots, m_k$ be pairwise relatively prime positive integers ( $\gcd(m_i, m_j) = 1$ for $i \neq j$ ).
The system:

\begin{aligned} x &\equiv a_1 \pmod{m_1} \\ x &\equiv a_2 \pmod{m_2} \\ &\vdots \\ x &\equiv a_k \pmod{m_k} \end{aligned}

has a unique solution modulo

M = m_1 m_2 \cdots m_k

Solution Formula:

x = \sum_{i=1}^{k} a_i M_i y_i \pmod{M}

Where:

$M = m_1 \times m_2 \times \dots \times m_k$
$M_i = M / m_i$
$y_i$ is the modular inverse of $M_i$ modulo $m_i$ (i.e., $M_i y_i \equiv 1 \pmod{m_i}$ ).

5. Fermat’s Little Theorem

Theorem Statement

If $p$ is a prime number and $a$ is an integer not divisible by $p$ (i.e., $\gcd(a, p) = 1$ ), then:

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

Alternative Form:
For any integer $a$ and prime $p$ :

a^p \equiv a \pmod{p}

Applications:

Simplifying powers: Computing $a^k \pmod{p}$ where $k$ is very large. You can reduce the exponent $k$ by modulo $(p-1)$ .
Finding Inverses: If $p$ is prime and $\gcd(a, p) = 1$ , then $a^{-1} \equiv a^{p-2} \pmod{p}$ .
Primality Testing: Used as a probabilistic test to check if a number is prime.

6. Cryptography Applications

Cryptography involves transforming a message (Plaintext, $P$ ) into an unreadable format (Ciphertext, $C$ ) using a Key.

Map of Alphabet to Integers

For these algorithms, we map standard English letters to integers:
A=0, B=1, C=2, ..., Z=25. The modulus is $m = 26$ .

Caesar Cipher

A shift cipher where each letter is shifted by a fixed number $k$ .

Encryption: $C \equiv (P + k) \pmod{26}$
Decryption: $P \equiv (C - k) \pmod{26}$
Key: The integer $k$ .

Example:
Shift $k=3$ .
Plaintext "A" (0) $\to (0+3) \pmod{26} = 3 \to$ Ciphertext "D".

Affine Cipher

A monoalphabetic substitution cipher using a linear function.

Encryption: $C \equiv (aP + b) \pmod{26}$
- $a$ and $b$ are the keys.
- Constraint: $\gcd(a, 26)$ must be $1$ for the cipher to be invertible (decryptable).
- Possible values for $a$ : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.
Decryption:
To decrypt, we solve for $P$ .

$C - b \equiv aP \pmod{26}$
Multiply by $a^{-1}$ (the modular inverse of $a$ modulo 26):
$P \equiv a^{-1}(C - b) \pmod{26}$

Example of Affine Decryption:
Let $C \equiv (7P + 3) \pmod{26}$ .
To decrypt, we need the inverse of $7 \pmod{26}$ .
Using Euclidean Algorithm, $7^{-1} \pmod{26} = 15$ (since $7 \times 15 = 105 = 4 \times 26 + 1$ ).
Decryption formula:

P \equiv 15(C - 3) \pmod{26}