Intermediate Number Theory
From cryptographic algorithms to quadratic reciprocity and p-adic fields
Intermediate (upper-undergraduate level)
About This Section
Intermediate number theory is organized in two parts. The applied/implementation part applies the theorems learned at the elementary level to cryptography and primality-testing algorithms, deepening understanding alongside Python implementations. The theoretical part studies deeper theories such as quadratic residues and the law of quadratic reciprocity, continued fractions, arithmetic functions, and p-adic number fields.
Prerequisites
- Elementary-level content (congruences, Euler's theorem, the Chinese remainder theorem, primitive roots)
- Basics of group theory (order, cyclic groups) recommended
Table of Contents
Applied / Implementation Part
Applies the theorems of the elementary level to cryptography and algorithms, with Python implementations.
A1. Congruences and Modular Arithmetic
Applications of congruences and their extensions to cryptography.
- Applications of Fermat's little theorem
- RSA and Diffie-Hellman
- Python implementation examples
A2. Applications of Euler's Totient Function
Computing the $\varphi$ function and generating RSA keys.
- Formulas for the $\varphi$ function
- Application to RSA key generation
- Python implementation examples
A3. Applications of the Chinese Remainder Theorem
CRT-RSA acceleration and security.
- Iterative CRT algorithm
- Faster decryption with CRT-RSA
- Python implementation examples
A4. The Discrete Logarithm Problem
The computational hardness underpinning cryptographic security.
- Baby-step Giant-step
- Pollard's rho
- Relation to Diffie-Hellman
A5. Miller-Rabin Primality Test
A probabilistic primality-testing algorithm.
- An improvement of the Fermat test
- Analysis of the misjudgment probability
- Implementation notes
A6. Binary GCD
Fast GCD via Stein's algorithm.
- Acceleration using bit operations
- Correctness proof and complexity
- Comparison with the Euclidean algorithm
A7. Elliptic Curves
Group structure and applications to cryptography.
- Definition of elliptic curves and the group operation
- The Mordell-Weil theorem
- Elliptic Curve Cryptography (ECC)
Theoretical Part
Deeper number-theoretic topics including quadratic residues, continued fractions, and p-adic number fields.
T1. Quadratic Residues and Reciprocity
The Legendre symbol, Euler's criterion, and Gauss's "jewel of mathematics".
T2. Distribution of Primes and the Prime Number Theorem
The prime-counting function $\pi(x)$, Chebyshev estimates, and the prime number theorem $\pi(x) \sim x/\ln x$.
T3. Arithmetic Functions
The divisor function $\sigma$, perfect numbers, and Dirichlet convolution.
T4. The Möbius Function
The Möbius function $\mu(n)$, the inversion formula, and the connection to Dirichlet series.
T5. Continued Fractions and Pell's Equation
Rational approximation and methods of solving $x^2 - Dy^2 = 1$.
T6. Quadratic Forms
Integers representable as $ax^2 + bxy + cy^2$. Fermat's two-square theorem. (Coming soon)
T7. p-adic Number Fields
The p-adic absolute value, the structure of $\mathbb{Q}_p$, and Hensel's lemma.
T8. Transcendental and Algebraic Irrational Numbers
The classification theory of numbers, Liouville's theorem, and Diophantine approximation.
- Algebraic irrationals and their conjugates
- Liouville, Hermite-Lindemann, Gelfond-Schneider
- Roth's theorem and irrationality measures
T9. Pythagorean Triples
Complete classification of integer solutions to $a^2 + b^2 = c^2$ and their geometric interpretation.
- Classification theorem for primitive Pythagorean triples
- Rational points on the unit circle
- Fermat's right-triangle theorem
Key Theorems
Applied / Implementation Part
Correctness of RSA
Let $n = pq$ (with $p, q$ prime) and $ed \equiv 1 \pmod{\varphi(n)}$. Then for every $m \in \mathbb{Z}/n\mathbb{Z}$,
$$m^{ed} \equiv m \pmod{n}$$This is a direct application of Euler's theorem $m^{\varphi(n)} \equiv 1$.
Error Probability of the Miller-Rabin Test
When $n$ is composite, a randomly chosen base $a$ misjudges "$n$ is prime" with probability at most $1/4$. After $k$ independent trials, the error probability is at most $(1/4)^k$.
Hasse's Theorem (Elliptic Curves)
For an elliptic curve $E$ over a finite field $\mathbb{F}_p$, the number of rational points $\#E(\mathbb{F}_p)$ satisfies
$$|\#E(\mathbb{F}_p) - (p+1)| \le 2\sqrt{p}$$Theoretical Part
The Prime Number Theorem
Let $\pi(x)$ denote the number of primes not exceeding $x$. Then
$$\pi(x) \sim \dfrac{x}{\ln x} \quad (x \to \infty)$$that is, $\displaystyle\lim_{x \to \infty} \dfrac{\pi(x)}{x/\ln x} = 1$. More precisely, $\pi(x) \sim \mathrm{Li}(x) = \int_2^x \dfrac{dt}{\ln t}$.
The Law of Quadratic Reciprocity
For distinct odd primes $p$ and $q$,
$$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\dfrac{p-1}{2}\cdot\dfrac{q-1}{2}}$$The Möbius Inversion Formula
If $f(n) = \sum_{d \mid n} g(d)$, then $g(n) = \sum_{d \mid n} \mu(d) f(n/d)$.
Here $\mu$ is the Möbius function.
Liouville's Theorem
If $\alpha$ is an algebraic irrational of degree $n$, then there is a constant $c(\alpha) > 0$ such that for every rational $p/q$,
$$\left|\alpha - \dfrac{p}{q}\right| > \dfrac{c(\alpha)}{q^n}$$Applications Accessible at This Level
Implementing Public-Key Cryptography
RSA uses Euler's totient function for key generation and the Chinese remainder theorem (CRT-RSA) for decryption. Diffie-Hellman key exchange relies on the hardness of the discrete logarithm problem. These cryptosystems can be fully understood from chapters A1-A4 of the applied part.
Primality Testing and Key Generation
Generating RSA keys requires large primes. The Miller-Rabin test (A5) is in practice the most widely used probabilistic primality test, and runs inside OpenSSL and GnuPG.
Signal Processing and Number-Theoretic Transforms
The number-theoretic transform (NTT) performs the FFT over a finite field, using primitive roots in place of roots of unity. It is free of floating-point error and is used in cryptography and large-integer multiplication.
Elliptic Curve Cryptography (ECC)
The discrete logarithm problem on an elliptic curve (A7) yields cryptosystems more efficient than RSA. ECDHE key exchange, standardized in TLS 1.3, and Bitcoin signatures (ECDSA) lie at the heart of modern Internet security.
Study Tips
- From theory to implementation: develop the skill of casting Euler's theorem and the CRT into concrete cryptographic algorithms
- Algorithmic complexity: compare and analyze the efficiency of algorithms such as Baby-step Giant-step and binary GCD
- Probabilistic methods: understand the significance and limitations of "probabilistically correct" algorithms such as Miller-Rabin
- Where algebra meets geometry: experience the synthesis of number theory, algebra, and geometry through elliptic curves