Unit 6: Number Theory and Its Application in Cryptography

MTH401 — Discrete Mathematics 6 min read

I. Foundations of Number Theory

Number theory studies integers and their relationships. Its cryptographic importance comes from arithmetic operations that are easy to perform but, for suitably large numbers, difficult to reverse without secret information.

A. Governing Principles and Conventions

The unit depends on precise notation for integers, divisibility, remainders, and congruence.

Integer domain: The symbol (\mathbb Z) denotes all integers:
[
\mathbb Z={\ldots,-2,-1,0,1,2,\ldots}.
]
Equality versus congruence: Equality means two integers have the same value; congruence means they have the same remainder under a specified modulus. Thus (17\ne5), but (17\equiv5\pmod{12}).
Modulus convention: In (a\bmod m), the modulus (m) is normally positive. The least nonnegative residue belongs to ({0,1,\ldots,m-1}).
Cryptographic principle: Plaintext is encoded numerically, transformed using modular arithmetic and a key, and recovered by applying an inverse transformation.
Closure: Integer addition, subtraction, and multiplication produce integers, allowing modular calculations to remain within a finite residue system.

II. Integer Relations

A. Divisibility and modular arithmetic

Divisibility describes exact integer multiplication, while modular arithmetic classifies integers according to their remainders.

Divisibility: For (a,b\in\mathbb Z), with (a\ne0), (a\mid b) means that (b=ak) for some (k\in\mathbb Z). For example, (6\mid42) because (42=6\cdot7).
Non-divisibility: The notation (a\nmid b) means no integer (k) satisfies (b=ak); for example, (5\nmid12).
Division algorithm: For integer (a) and positive integer (m), unique integers (q,r) exist such that:
TEXT
```
  a = mq + r, where 0 <= r < m
```
Here (q) is the quotient and (r) is the remainder.
Congruence: For integers (a,b) and (m>0):
TEXT
```
  a ≡ b (mod m) exactly when m | (a - b)
```
Thus (38\equiv3\pmod7), since (7\mid35).

Arithmetic rules: If (a\equiv b\pmod m) and (c\equiv d\pmod m), then:

TEXT

  a + c ≡ b + d (mod m)
  a - c ≡ b - d (mod m)
  ac ≡ bd (mod m)

Cancellation restriction: From (ac\equiv bc\pmod m), cancellation of (c) is valid when (\gcd(c,m)=1). Division is therefore not automatically permitted.

III. Fundamental Integer Building Blocks

A. Primes

A prime is an integer greater than (1) whose only positive divisors are (1) and itself.

Prime and composite numbers: The numbers (2,3,5,7) are prime; (12) is composite because (12=3\cdot4). The integer (1) is neither prime nor composite.
Fundamental theorem of arithmetic: Every integer (n>1) is either prime or has a factorization into primes that is unique apart from factor order.
Example factorization:
TEXT
```
  360 = 2^3 × 3^2 × 5
```
The exponents give the multiplicities of the prime factors.
Testing principle: A composite (n) has a prime divisor not exceeding (\sqrt n). To test (97), it is sufficient to check divisibility by (2,3,5,) and (7).
Cryptographic role: Systems such as RSA use products of large primes because multiplication is efficient while recovering the prime factors of a sufficiently large product is computationally difficult.

IV. Common Divisors and Multiples

A. Greatest common divisors and least common multiples

The greatest common divisor measures shared factors, while the least common multiple gives the smallest shared positive multiple.

Greatest common divisor: (\gcd(a,b)) is the greatest positive integer dividing both nonzero integers (a) and (b).
Coprimality: Integers (a) and (b) are relatively prime when (\gcd(a,b)=1); for example, (\gcd(8,15)=1).
Least common multiple: (\operatorname{lcm}(a,b)) is the least positive integer divisible by both (a) and (b).
Product relation: For positive integers (a,b):
TEXT
```
  gcd(a,b) × lcm(a,b) = ab
```
Prime-exponent method: The gcd uses the minimum exponent of each shared prime, whereas the lcm uses the maximum exponent appearing in either number.
Worked example: Since (24=2^3\cdot3) and (36=2^2\cdot3^2),
TEXT
```
  gcd(24,36) = 2^2 × 3 = 12
  lcm(24,36) = 2^3 × 3^2 = 72
```

V. Efficient GCD Computation

A. Euclidean algorithm

The Euclidean algorithm repeatedly replaces a pair of integers by the divisor and remainder without changing their gcd.

Core identity: If (a=bq+r), then:
TEXT
```
  gcd(a,b) = gcd(b,r)
```
Here (a,b,q,r\in\mathbb Z), (b>0), and (0\le r<b).
Procedure: Divide the larger number by the smaller, replace the pair with the smaller number and nonzero remainder, and repeat. The last nonzero remainder is the gcd.

Worked example:

TEXT

  252 = 105(2) + 42
  105 = 42(2) + 21
  42  = 21(2) + 0
  gcd(252,105) = 21

Efficiency: Remainders decrease strictly, so the algorithm terminates and avoids prime factorization.
Extended form: Recording substitutions during the algorithm expresses the gcd as a linear combination of the original integers.

VI. Linear Combination of Integers

A. Bezout's lemma

Bezout's lemma states that the gcd of two integers can be expressed as an integer linear combination of them.

Formal statement: For nonzero integers (a,b), there exist (x,y\in\mathbb Z) such that:
TEXT
```
  ax + by = gcd(a,b)
```
The integers (x) and (y) are Bezout coefficients.
Coprime case: If (\gcd(a,b)=1), then some integers (x,y) satisfy (ax+by=1).
Derivation by substitution: From the Euclidean calculation:
TEXT
```
  21 = 105 - 42(2)
  42 = 252 - 105(2)
```
substitution gives:
TEXT
```
  21 = 105(5) - 252(2)
```
Solvability consequence: The equation (ax+by=c) has integer solutions exactly when (\gcd(a,b)\mid c).
Cryptographic significance: Bezout coefficients calculate modular inverses, which are required for affine decryption and public-key algorithms.

VII. Modular Equations

A. Linear congruence

A linear congruence seeks integers (x) satisfying (ax\equiv b\pmod m).

Equivalent equation: The congruence means (m\mid(ax-b)), or:
TEXT
```
  ax - my = b
```
for some integer (y).
Existence condition: Let (d=\gcd(a,m)). Solutions exist exactly when (d\mid b).
Number of solutions: If (d\mid b), there are exactly (d) incongruent solutions modulo (m).
Reduction: Dividing (a), (b), and (m) by (d) produces a congruence whose coefficient and modulus are coprime.
Worked example: For (6x\equiv9\pmod{15}), (d=\gcd(6,15)=3), and (3\mid9). Reduction gives:
TEXT
```
  2x ≡ 3 (mod 5)
  x ≡ 4 (mod 5)
```
Hence modulo (15), the three solutions are (x\equiv4,9,14).

VIII. Reversible Modular Multiplication

A. Inverse of a modulo m

A modular inverse of (a) modulo (m) is an integer that reverses multiplication by (a).

Definition: An integer (a^{-1}) satisfies:
TEXT
```
  aa^(-1) ≡ 1 (mod m)
```
where (m>1).
Existence criterion: The inverse exists exactly when (\gcd(a,m)=1).
Bezout connection: If (ax+my=1), reduction modulo (m) gives (ax\equiv1\pmod m); therefore, (x) is an inverse of (a).
Worked example: The Euclidean algorithm gives:
TEXT
```
  26 = 7(3) + 5
  7 = 5(1) + 2
  5 = 2(2) + 1
```
Back-substitution yields (1=26(3)-7(11)). Therefore,
TEXT
```
  7^(-1) ≡ -11 ≡ 15 (mod 26)
```
Uniqueness: When an inverse exists, it is unique modulo (m).

IX. Simultaneous Congruences

A. Chinese remainder theorem

The Chinese remainder theorem combines congruences with pairwise coprime moduli into one congruence.

Formal statement: If (m_1,\ldots,m_k) are pairwise coprime positive integers, then:
TEXT
```
  x ≡ a_i (mod m_i), for i = 1,...,k
```
has a unique solution modulo (M=m_1m_2\cdots m_k).
Construction: Define (M_i=M/m_i), and choose (y_i) satisfying (M_iy_i\equiv1\pmod{m_i}). Then:
TEXT
```
  x ≡ Σ(a_i M_i y_i) (mod M)
```
Worked example: For (x\equiv2\pmod3) and (x\equiv3\pmod5), (M=15). Using (M_1=5,\ y_1=2) and (M_2=3,\ y_2=2):
TEXT
```
  x ≡ 2(5)(2) + 3(3)(2) ≡ 38 ≡ 8 (mod 15)
```
Application: CRT can replace one computation modulo a large composite number with several smaller computations, improving efficiency in cryptographic implementations.
Limitation: Without pairwise coprime moduli, compatibility conditions are required and uniqueness is modulo the lcm rather than necessarily the product.

X. Classical Substitution Cryptography

A. Encryption and decryption by Caesar cipher and affine transformation

These ciphers encode letters as residues and use reversible modular functions to transform plaintext into ciphertext.

Caesar cipher: This cipher shifts every letter by a fixed key (k).
- Encoding: Assign (A=0,B=1,\ldots,Z=25), and use:
  TEXT
```
     Encryption: E_k(x) = (x + k) mod 26
     Decryption: D_k(y) = (y - k) mod 26
```
  Here (x) is plaintext, (y) is ciphertext, and (k) is the shift.
- Example: With (k=3), (C=2) becomes (F=(2+3)\bmod26=5).
- Limitation: Only (26) shifts exist, so exhaustive key search and frequency analysis defeat the cipher easily.
Affine transformation: This cipher combines multiplication and addition:
- Functions:
  TEXT
```
     Encryption: E(x) = (ax + b) mod 26
     Decryption: D(y) = a^(-1)(y - b) mod 26
```
  Here ((a,b)) is the key and (a^{-1}) is the inverse of (a) modulo (26).
- Key condition: Decryption is possible only when (\gcd(a,26)=1). Thus (a) must be one of (1,3,5,7,9,11,15,17,19,21,23,25).
- Contrast: Caesar encryption is the affine case (a=1); multiplication enlarges the affine key space but does not prevent frequency analysis.

XI. Prime-Modulus Exponentiation

A. Fermat's little theorem

Fermat's little theorem simplifies powers modulo a prime and provides a theoretical basis for modular inverses and cryptography.

Formal statement: If (p) is prime and (p\nmid a), then:
TEXT
```
  a^(p-1) ≡ 1 (mod p)
```
Here (a\in\mathbb Z) and (p) is prime.
Equivalent form: For every integer (a) and prime (p):
TEXT
```
  a^p ≡ a (mod p)
```
Inverse consequence: If (p\nmid a), multiplying (a^{p-1}\equiv1\pmod p) as (a\cdot a^{p-2}) shows:
TEXT
```
  a^(-1) ≡ a^(p-2) (mod p)
```
Worked example: To find (3^{100}\bmod7), use (3^6\equiv1\pmod7). Since (100=6(16)+4):
TEXT
```
  3^100 ≡ (3^6)^16 × 3^4 ≡ 1 × 81 ≡ 4 (mod 7)
```
Primality limitation: Failure of (a^{n-1}\equiv1\pmod n) proves that (n) is composite, but passing this test alone does not guarantee that (n) is prime.