Number Theory and Cryptographic Mathematics

Introduction and Context

Number theory studies the properties of integers, especially divisibility, prime numbers, and congruences. Although many of its questions appear purely theoretical, number theory is central to modern computing. Public-key encryption, digital signatures, authentication protocols, pseudorandom constructions, error-correcting codes, and post-quantum cryptography all depend on mathematical structures involving integers or finite fields.

Cryptography does not usually aim to make information mathematically impossible to recover. Instead, it constructs computational problems that are easy to perform in one direction but believed to be infeasible to reverse without secret information. This distinction between mathematical difficulty and practical computational cost is fundamental. A cryptographic system is secure only relative to an attacker model, an algorithmic environment, and a specified security parameter.

This chapter develops the number-theoretic tools needed to understand these systems: divisibility, primes, greatest common divisors, modular arithmetic, Euclidean algorithms, modular exponentiation, finite fields, and the foundations and limitations of classical and post-quantum cryptography.

Learning Objectives

By the end of this chapter, a student should be able to:

1. Apply divisibility rules, prime factorization, and the Fundamental Theorem of Arithmetic.
2. Use the Euclidean and extended Euclidean algorithms to compute greatest common divisors and modular inverses.
3. Solve basic linear congruences and apply the Chinese Remainder Theorem.
4. Perform modular exponentiation efficiently and explain Euler’s and Fermat’s theorems.
5. Describe finite fields and distinguish prime fields from extension fields.
6. Explain the mathematical structure of RSA, Diffie–Hellman, elliptic-curve cryptography, and digital signatures.
7. Evaluate the assumptions, implementation risks, and limitations of classical cryptography.
8. Explain why quantum algorithms threaten some classical systems and how post-quantum schemes use alternative mathematical problems.

1. Divisibility and Prime Numbers

For integers a and b, with a ≠ 0, we say that a divides b, written a | b, if there exists an integer k such that b = ak. The integer a is a divisor of b, while b is a multiple of a. For example, 7 | 35 because 35 = 7 × 5.

Divisibility has several useful properties. If a | b and a | c, then a | (b + c) and a | (b − c). If a | b and b | c, then a | c. These properties support algebraic manipulation of integer expressions and the correctness of many cryptographic algorithms.

The division algorithm states that for integers a and b, with b > 0, there exist unique integers q and r such that

Here, a is the dividend, b is the divisor, q is the quotient, and r is the remainder. For example, dividing 47 by 9 gives 47 = 9 × 5 + 2.

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. The first primes are 2, 3, 5, 7, 11, and 13. An integer greater than 1 that is not prime is composite.

The Fundamental Theorem of Arithmetic states that every integer n > 1 can be expressed uniquely, apart from the order of factors, as a product of primes:

The pᵢ are distinct primes and the eᵢ are positive integers. This theorem makes prime factorization a canonical representation of an integer. The security of RSA depends partly on the practical difficulty of factoring a large product of two carefully selected primes.

2. Greatest Common Divisors and Bézout’s Identity

The greatest common divisor of integers a and b, not both zero, is the largest positive integer dividing both. It is written gcd(a, b). Two integers are relatively prime, or coprime, when their greatest common divisor is 1.

Bézout’s identity states that there exist integers x and y such that

The coefficients x and y are called Bézout coefficients. This identity is especially important because, when gcd(a, n) = 1, the coefficient x gives a multiplicative inverse of a modulo n.

The Euclidean Algorithm

The Euclidean algorithm repeatedly applies the division algorithm:

The last nonzero remainder is gcd(a, b). The algorithm is efficient: its number of divisions grows on the order of the logarithm of the input values.

Worked Example: gcd(252, 105)

Therefore, gcd(252,105) = 21. Back-substitution gives

Thus Bézout coefficients are x = −2 and y = 5 for the equation 21 = 252x + 105y.

3. Modular Arithmetic and Congruences

For integers a, b, and positive integer n, we say that a is congruent to b modulo n, written a ≡ b (mod n), when n divides a − b. Equivalently, a and b have the same remainder upon division by n.

For example, 29 ≡ 5 (mod 12) because 29 − 5 = 24, and 12 divides 24. Modular arithmetic treats numbers that differ by multiples of n as equivalent. The set of residue classes modulo n is denoted ℤ_n or ℤ/nℤ.

Congruences are compatible with addition and multiplication:

Consequently, polynomial expressions may be reduced modulo n during calculation. Division is different: it is valid only when the divisor has a multiplicative inverse modulo n.

An integer a has a modular inverse modulo n if there is an integer a⁻¹ satisfying

Such an inverse exists if and only if gcd(a,n) = 1. For example, 3 has inverse 7 modulo 10 because 3 × 7 = 21 ≡ 1 (mod 10). The number 2 has no inverse modulo 10 because gcd(2, 10) = 2.

Solving Linear Congruences

Consider ax ≡ b (mod n). Let d = gcd(a,n). A solution exists if and only if d divides b. If a solution exists, there are d distinct solution classes modulo n.

If d = 1, multiply both sides by the inverse of a modulo n:

For example, solve 7x ≡ 5 (mod 12). Since 7 × 7 = 49 ≡ 1 (mod 12), the inverse of 7 is 7. Therefore,

4. Extended Euclidean Algorithm

The extended Euclidean algorithm computes both gcd(a, b) and Bézout coefficients. It is therefore the standard method for finding modular inverses.

Worked Example: Inverse of 17 modulo 43

Applying the Euclidean algorithm:

Back-substitution gives

Thus (−5) × 17 ≡ 1 (mod 43). The inverse is 17⁻¹ ≡ 38 (mod 43).

In software, modular inversion should use a tested integer algorithm rather than floating-point division. Floating-point approximations can produce incorrect results for large integers because not all integers can be represented exactly.

5. Euler’s Totient, Fermat’s Theorem, and Exponent Reduction

Euler’s totient function φ(n) counts the integers in {1, 2, …, n} that are relatively prime to n. If p is prime,

If p and q are distinct primes,

More generally, if the prime factorization of n is n = p₁^e₁⋯pₖ^eₖ, then

Euler’s theorem states that if gcd(a, n) = 1, then

Fermat’s little theorem is the prime-modulus special case. If p is prime and p does not divide a, then

These theorems are useful for proving cryptographic correctness, but they do not themselves guarantee security. Security depends on the difficulty of reversing or exploiting the associated operations.

6. Efficient Modular Exponentiation

Directly computing a^e is inefficient when e is large. Repeated squaring reduces the number of multiplications to approximately logarithmic in e. Write the exponent in binary and repeatedly square the base, reducing modulo n after each operation.

Worked Example: Compute 7¹³ mod เต?

We compute modulo 20:

Since 13 = 8 + 4 + 1,

In practice, cryptographic implementations use square-and-multiply, often combined with constant-time techniques. A naïve implementation may reveal exponent bits through timing, memory access, or power consumption.

7. The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) states that if n₁, n₂, …, nₖ are pairwise coprime, then the system

has a unique solution modulo N = n₁n₂⋯nₖ.

Example

Solve

Numbers congruent to 2 modulo 3 are 2, 5, 8, 11, …; among them, 8 is congruent to 3 modulo 5. Thus x ≡ 8 (mod 15).

CRT is used to accelerate RSA decryption by replacing one computation modulo a large number with two computations modulo its prime factors. This optimization must be protected against fault attacks: an attacker may infer secret factors if faulty outputs are not detected.

8. Finite Fields

A field is a set with addition, subtraction, multiplication, and division by every nonzero element, satisfying familiar algebraic laws. A finite field contains finitely many elements. A finite field has order p^m, where p is prime and m is a positive integer.

The simplest finite field is the prime field 𝔽_p, consisting of integers modulo p, with p prime. Every nonzero element has an inverse because no nonzero residue shares a factor with p.

For example, 𝔽₅ = {0,1,2,3,4}. The inverse of 2 is 3 because 2 × 3 ≡ 1 (mod 5).

Extension fields 𝔽_p^m can be constructed using polynomials over 𝔽_p. Choose an irreducible polynomial f(x) of degree m and perform polynomial arithmetic modulo f(x). The irreducibility condition ensures that every nonzero element has an inverse.

Finite fields are important in coding theory, symmetric cryptography, and elliptic-curve systems. For example, the Advanced Encryption Standard operates on bytes interpreted using arithmetic related to 𝔽_2⁸.

9. Classical Public-Key Cryptography

RSA

RSA selects two large primes p and q and computes

Choose a public exponent e satisfying gcd(e,φ(n)) = 1. Compute d such that

The public key is (n, e), and the private key contains d and normally p and q. For a message representative m, encryption is

and decryption is

Correctness follows from the relationship between e and d and Euler-type results, with additional care for messages not relatively prime to n. Real systems do not use textbook RSA directly. Secure padding schemes, such as OAEP for encryption and PSS for signatures, are essential.

RSA security is associated with integer factorization, but the exact relationship between breaking RSA and factoring is subtle. Small keys, poor prime generation, predictable randomness, incorrect padding, and side-channel leakage can all cause failure even if factoring remains difficult.

Diffie–Hellman Key Exchange

Let G be a cyclic group with generator g. Alice selects secret a and sends A = g^a. Bob selects secret b and sends B = g^b. Both compute

because B^a = (g^b)^a = g^ab and A^b = (g^a)^b = g^ab.

The adversary sees g, g^a, and g^b, but is assumed unable to compute g^ab efficiently. This is the computational Diffie–Hellman assumption in the relevant group.

Unauthenticated Diffie–Hellman is vulnerable to a man-in-the-middle attack. A secure protocol must authenticate public values, for example through certificates or digital signatures.

Elliptic-Curve Cryptography

An elliptic curve over a suitable field can be written in a simplified form such as

where the curve parameters satisfy conditions that prevent singularities. The points on the curve, together with a special point at infinity, form an abelian group under a geometrically defined addition operation.

Elliptic-curve cryptography uses scalar multiplication kP, meaning P is added to itself k times. Computing kP is efficient when k is known, while recovering k from P and kP is believed difficult for appropriately chosen curves. ECC provides comparable security with smaller keys than traditional RSA, but implementation must use standardized curves, validated points, safe random generation, and side-channel-resistant arithmetic.

10. Digital Signatures and Hash Functions

Encryption primarily provides confidentiality; digital signatures provide authenticity, integrity, and non-repudiation within an appropriate legal and operational framework. A signature scheme consists of key generation, signing, and verification algorithms.

A cryptographic hash function maps an arbitrary-length input to a fixed-length digest. Important properties include preimage resistance, second-preimage resistance, and collision resistance. Hash functions are not encryption: they are generally designed to be one-way and do not use a decryption key.

A secure signature system signs a structured representation, often a hash of the message, rather than an unprocessed message. However, hashing alone does not authenticate a sender. Anyone can hash a message; authentication requires a secret signing key and a trusted public-key distribution mechanism.

11. Security Models and Limitations

Cryptographic mathematics operates under assumptions. A system may rely on:

• computational hardness, such as factoring or discrete logarithms;
• secure random number generation;
• correct parameter selection;
• authenticated key management;
• resistance to chosen-plaintext and chosen-ciphertext attacks;
• secure implementation and protocol composition.

A mathematically correct algorithm can be insecure in practice. Common causes include weak passwords, reused nonces, predictable keys, insufficient key length, outdated algorithms, certificate-validation errors, and side-channel attacks.

Security must also account for computational resources. A problem may be theoretically solvable but practically infeasible for current hardware. Conversely, advances in algorithms or hardware can change the security margin. Therefore, cryptographic standards specify security levels, parameter sizes, approved modes, and transition guidance.

12. Quantum Computing and Post-Quantum Cryptography

Large fault-tolerant quantum computers would threaten widely deployed public-key systems. Shor’s algorithm can solve integer factorization and discrete logarithm problems in polynomial time on a quantum computer. Thus RSA, finite-field Diffie–Hellman, and elliptic-curve cryptography cannot be regarded as long-term quantum-resistant.

Grover’s algorithm provides a quadratic speedup for unstructured search. Its effect on symmetric cryptography is less devastating: approximately doubling the key length can often restore a comparable brute-force security margin, subject to implementation and model assumptions.

Post-quantum cryptography (PQC) seeks algorithms that run on classical computers but are believed resistant to both classical and quantum attacks. Major families include:

A prominent lattice-based concept is the Learning With Errors problem. In simplified form, an attacker receives samples resembling

where a is public, s is secret, e is a small error, q is a modulus, and ⟨a,s⟩ is an inner product. The noise e makes inversion difficult. The exact security of a scheme depends on its construction, parameter choices, reduction results, and implementation.

PQC does not mean that every post-quantum proposal is automatically secure. New algorithms require cryptanalysis, implementation testing, standardization, and long-term review. Migration also creates engineering challenges because post-quantum keys, signatures, and ciphertexts may be larger than classical equivalents.

13. Applied Case: Planning a Secure Migration for a University

Background

This illustrative case concerns a university operating a student portal, research-data repositories, virtual private networks, and a certificate authority. Several services use RSA and elliptic-curve key exchange.

Problem

The university must protect confidential student and research data over many years. Although large-scale quantum computers are not currently available, an adversary could record encrypted traffic today and attempt to decrypt it later. This is known as a “harvest now, decrypt later” risk.

Analysis

The security team inventories algorithms, key sizes, certificate dependencies, data-retention periods, and cryptographic libraries. It identifies long-lived research records as more exposed than short-lived public web sessions. It also checks whether systems support algorithm agility and whether certificates can accommodate hybrid key exchange.

The team distinguishes three issues:

1. RSA and ECC are vulnerable to a sufficiently capable quantum computer.
2. Symmetric encryption and hashing generally require parameter review rather than immediate replacement by public-key alternatives.
3. Migration failure may result from poor certificate management or incompatible software, even when the selected mathematics is sound.

Approach and Solution

The university adopts a staged plan. It first upgrades classical cryptography to current standards, removes obsolete algorithms, and improves random-number generation. It then pilots hybrid key establishment, combining a classical method with a standardized post-quantum method. Sensitive data are re-encrypted according to retention requirements, and cryptographic dependencies are recorded in a central inventory.

The university also establishes key rotation, incident-response procedures, code-review requirements, and independent testing. Staff are trained to distinguish encryption, signatures, hashing, and authentication.

Outcome

The transition reduces long-term exposure while preserving interoperability during the migration period. The university can replace one algorithm without redesigning every application because cryptographic interfaces were separated from application logic.

Learning Points

Cryptographic migration is a governance and systems-engineering problem as well as a mathematical problem. Organizations should identify data longevity, maintain algorithm agility, test implementations, and monitor standards. A theoretically strong algorithm cannot compensate for unmanaged keys or unauthenticated protocols.

14. Best Practices for Computing Professionals

Use established, peer-reviewed cryptographic libraries rather than implementing primitives from scratch. Select algorithms and parameters from current standards. Generate keys with a cryptographically secure random number generator. Never reuse nonces where a scheme forbids reuse. Authenticate key exchange. Protect private keys with access controls and hardware-backed storage where appropriate.

Use constant-time implementations for sensitive operations when feasible, validate all public inputs, and apply fault detection to optimized algorithms such as CRT-RSA. Separate cryptographic APIs from business logic. Document algorithms, key lifetimes, trust anchors, and recovery procedures. Plan for post-quantum migration before long-lived data becomes impossible to protect.

Ethically, professionals must treat cryptographic failures as risks to privacy, safety, and institutional trust. Legal requirements may govern personal data, financial information, health records, or cross-border transfers. Security decisions should therefore include risk assessment, accountability, auditability, and responsible disclosure.

Chapter Summary

Number theory supplies the language and mechanisms of cryptographic computation. Divisibility and prime factorization establish the structure of integers. The Euclidean algorithm computes greatest common divisors, while the extended algorithm produces Bézout coefficients and modular inverses. Congruences permit arithmetic over residue classes, and Euler’s theorem and Fermat’s little theorem explain important exponentiation identities. Repeated squaring makes modular exponentiation practical, while the Chinese Remainder Theorem supports decomposition and optimization.

Finite fields provide algebraic settings in which addition, multiplication, and inversion are well defined. RSA relies on modular exponentiation and the practical difficulty of factoring; Diffie–Hellman relies on discrete-logarithm-related assumptions; elliptic-curve systems use group operations on curve points. Digital signatures and hash functions address authenticity and integrity rather than merely confidentiality.

Classical cryptography is limited by mathematical advances, implementation errors, weak randomness, side channels, and protocol failures. Quantum algorithms threaten factoring and discrete logarithms, motivating post-quantum approaches based on lattices, codes, hashes, and other structures. Secure practice requires both mathematical understanding and disciplined engineering, governance, and migration planning.

Key Terms

Divisibility: The relation a | b meaning that b is an integer multiple of a.

Prime number: An integer greater than 1 with exactly two positive divisors.

Fundamental Theorem of Arithmetic: The theorem that every integer greater than 1 has a unique prime factorization.

Greatest common divisor: The largest positive integer dividing two given integers.

Bézout’s identity: The identity gcd(a,b) = ax + by.

Euclidean algorithm: An efficient procedure for computing a greatest common divisor.

Congruence: Equality of two integers modulo a specified modulus.

Modular inverse: An element that multiplies another element to give 1 modulo n.

Euler’s totient function: The number of positive integers up to n that are coprime to n.

Fermat’s little theorem: An exponentiation theorem for prime moduli.

Modular exponentiation: Computing powers while repeatedly reducing modulo a modulus.

Chinese Remainder Theorem: A theorem giving a unique solution for compatible congruences with pairwise coprime moduli.

Finite field: A finite algebraic field with well-defined addition, multiplication, and inverses.

RSA: A public-key cryptosystem associated with integer factorization.

Diffie–Hellman exchange: A protocol for establishing a shared secret using exponentiation in a group.

Elliptic-curve cryptography: Cryptography based on group operations on elliptic-curve points.

Digital signature: A cryptographic mechanism for authenticity and integrity.

Post-quantum cryptography: Cryptography designed to resist attacks by classical and quantum computers.

Side-channel attack: An attack exploiting implementation leakage such as timing, power, or memory behavior.

Algorithm agility: The ability to replace cryptographic algorithms without redesigning an entire system.

Review Questions

Short Answer Questions

1. Define the relation a | b and give one example.
2. What condition guarantees that a has an inverse modulo n?
3. State Euler’s theorem and its applicability condition.
4. Why is repeated squaring used in cryptographic computation?
5. Name two mathematical problems threatened by Shor’s algorithm.

Long Answer Questions

1. Explain the Euclidean and extended Euclidean algorithms and show how the latter computes a modular inverse.
2. Describe the Chinese Remainder Theorem and explain one cryptographic use of it.
3. Explain the mathematical workflow of RSA from key generation through encryption and decryption.
4. Compare RSA, finite-field Diffie–Hellman, and elliptic-curve cryptography in terms of underlying structures and assumptions.
5. Explain why a mathematically correct cryptographic algorithm may still be insecure in a real implementation.

Analytical / Application Questions

1. A system uses RSA to protect data that must remain confidential for twenty years. Analyze the risks posed by quantum computing and propose a migration strategy.
2. A developer implements modular inversion using floating-point division. Explain why this is unsafe and recommend a mathematically appropriate alternative.
3. A key-exchange protocol uses unauthenticated Diffie–Hellman. Construct a man-in-the-middle scenario and identify the control needed to prevent it.

Multiple Choice Questions with Answers

Question 1

Which condition is necessary and sufficient for a to have a multiplicative inverse modulo n?

A. a is prime

B. n is even

C. gcd(a,n) = 1

D. a < n

Correct Answer: C. gcd(a,n) = 1

Question 2

What is gcd(252, 105)?

A. 7

B. 21

C. 42

D. 63

Correct Answer: B. 21

Question 3

What is the inverse of 17 modulo 43?

A. 5

B. 17

C. 26

D. 38

Correct Answer: D. 38

Question 4

What is 7¹³ modulo 20?

A. 1

B. 7

C. 13

D. 19

Correct Answer: B. 7

Question 5

The Chinese Remainder Theorem guarantees a unique solution modulo the product of the moduli when the moduli are what?

A. All prime powers

B. Pairwise coprime

C. All even

D. Equal

Correct Answer: B. Pairwise coprime

Question 6

Which operation is central to RSA encryption?

A. Matrix inversion over the real numbers

B. Modular exponentiation

C. Sorting prime numbers

D. Floating-point division

Correct Answer: B. Modular exponentiation

Question 7

What is the main security concern with unauthenticated Diffie–Hellman exchange?

A. It cannot perform multiplication

B. It reveals every private exponent immediately

C. It is vulnerable to a man-in-the-middle attack

D. It requires no random values

Correct Answer: C. It is vulnerable to a man-in-the-middle attack

Question 8

Which structure is used directly by elliptic-curve cryptography?

A. A group of points on an elliptic curve

B. A list of decimal fractions

C. A matrix of real eigenvalues

D. A queue of passwords

Correct Answer: A. A group of points on an elliptic curve

Question 9

Which quantum algorithm threatens RSA and elliptic-curve cryptography by efficiently addressing their underlying problems?

A. Dijkstra’s algorithm

B. Shor’s algorithm

C. PageRank

D. Huffman coding

Correct Answer: B. Shor’s algorithm

Question 10

Which is a post-quantum cryptographic family?

A. Lattice-based cryptography

B. Classical substitution ciphers only

C. Unkeyed compression

D. Floating-point hashing

Correct Answer: A. Lattice-based cryptography