Engineering

The LLL Lattice Basis Reduction Algorithm

The LLL algorithm: size reduction interleaved with swaps under the Lovasz condition, and the guarantees it provides in polynomial time.

The Logarithmic Embedding and the Unit Lattice

Mapping units into a real vector space by logarithms of conjugate absolute values, and the lattice this produces.

The Matrix (Regular) Representation of Algebraic Numbers

Representing a field element by its multiplication matrix, and reading trace, norm and characteristic polynomial off that matrix.

Engineering Mathematics13 Aug 2026 · 22 min read

The Matrix-Vector Product

The matrix-vector product defined as a linear combination of the columns of a matrix, the equation Ax = b for a linear system, and when equal products force equal matrices.

The Maximal Order Problem

The maximal order problem, its reduction to a prime-by-prime question, and the factoring obstruction that limits it.

The Miller-Rabin Primality Test

The Miller-Rabin test, the witness structure, the one-quarter bound, and why it is the practical standard.

The Modern Primality Testing Landscape

The methods available for proving primality, their complexities, and which to use for a given size of candidate.

The Multiple Polynomial Quadratic Sieve

MPQS: using many polynomials with short intervals to keep values small, and the self-initialising variant.

Engineering Mathematics13 Aug 2026 · 21 min read

The Norm of a Vector

The norm of a vector: definition from the moduli of its entries, its identity with the inner product, positive definiteness, unit vectors and stable computation.

The Number Field Sieve and Factoring Records

The number field sieve, the current state of factoring records, and how key size recommendations follow from them.

The Order of a Group Element

The order of an element, its relationship to the group order, and the computational cost of determining it.

The Pocklington-Lehmer N-1 Primality Test

Proving primality from a partial factorisation of one less than the candidate, and the certificate this produces.

The Pohst-Zassenhaus Theorem

The theorem underlying maximal order computation: enlarging an order by the ring of multipliers of its radical.

The Pollard p-1 Method

Pollard's p-1 method, its dependence on the smoothness of the group order, and why that dependence is its fatal limitation.

The Pollard Rho Factoring Method

Pollard's rho method: cycle detection in a pseudorandom sequence, the birthday bound, and Brent's improvement.

The Polynomial Euclidean Algorithm over a Field

The Euclidean and extended Euclidean algorithms for polynomials over a field, and their role in inversion and interpolation.

The Polynomial Reduction Algorithm

Finding a small defining polynomial for a number field using lattice reduction on the maximal order, and why this pays for itself.

The Prime Number Theorem

The prime number theorem, its equivalent formulations, and the logarithmic integral as the superior approximation.

The Quadratic Residuosity Assumption

The quadratic residuosity assumption, its use in probabilistic encryption, and its relationship to factoring.

The Quadratic Sieve Algorithm

The quadratic sieve: candidate generation near the square root, sieving for smoothness, and its practical range.

The Quadratic Sieve: Linear Algebra Stage

Finding dependencies in the relation matrix over the field with two elements, and why this stage is the practical bottleneck.

The Quadratic Sieve: Sieving Stage

The sieving stage: identifying smooth polynomial values in bulk using logarithm accumulation rather than trial division.

The Regulator: Definition and Computation

The regulator as the covolume of the unit lattice, its computation, and the precision and verification it demands.

The Resolvent Method for Galois Groups

Constructing resolvent polynomials whose factorisation distinguishes candidate Galois groups, and the practical issues in using them.

The Round 2 Maximal Order Algorithm

The Round 2 algorithm: computing the maximal order prime by prime via radicals and rings of multipliers.

Engineering Mathematics13 Aug 2026 · 25 min read

The Row-Reducing Algorithm (Gauss-Jordan Elimination)

The algorithm that drives any matrix to reduced row-echelon form: pivot search, interchange, normalisation, column clearing, cost and pivoting strategy.

The RSA Cryptosystem

RSA key generation, encryption, decryption and correctness, together with the assumptions its security depends on.

The Schnorr-Lenstra Class Group Factoring Method

Factoring via class groups of quadratic orders, and its place as the conceptual bridge to the elliptic curve method.

The Sieve of Eratosthenes

The classical sieve for enumerating primes, its complexity, segmented variants, and its role as a precomputation step.

The Smith Normal Form Algorithm

The Smith normal form, its computation by alternating row and column reduction, and the invariant factors it exposes.

Engineering Mathematics13 Aug 2026 · 21 min read

The Span of a Set in a Vector Space

Linear combinations and spans in an abstract vector space: the definition, the proof that a span is always a subspace, and how membership becomes a linear system.

The Standard Representation of Algebraic Numbers

Representing field elements as coefficient vectors relative to a power basis or integral basis, with a common denominator.

The Structure of Finite Abelian Groups

The structure theorem decomposing every finite abelian group into cyclic factors, and its computational consequences.

The Structure of the Group of Units Modulo n

The structure of Z_n* as a product of cyclic groups, the Carmichael function, and why prime moduli behave differently.

The Sub-exponential Algorithm in Practice

Practical considerations in running class group computations: parameter tuning, parallelism, precision management and diagnostics.

The Sub-Resultant GCD Algorithm

The sub-resultant remainder sequence: predicting the divisible factor at each step to keep coefficients near minimal without content computation.

The Subfield Problem

Finding the subfields of a number field, by lattice methods and by linear algebra over the complex numbers.

Trace, Norm and the Characteristic Polynomial

Trace, norm and characteristic polynomial of a field element, their computation, and their use as invariants and cross-checks.

Trial Division and Basic Primality Testing

Trial division as a primality test and as a filter, its exponential cost, and the role it still plays in practice.

Trial Division and Lehman's Method

Trial division as the first factoring step, its cost, and Lehman's improvement on Fermat's method.

Trial Division up to a Small Bound

Choosing the trial division bound ahead of a probabilistic test, and the cost balance that determines it.

Unique Factorisation Domains, Content and Primitive Parts

Content and primitive part, Gauss's lemma, and why factoring over the rationals reduces to factoring over the integers.

Unique Factorization Domains

Unique factorisation domains, the distinction between irreducible and prime, and the standard examples and counterexamples.

Unique Factorization in Euclidean and Principal Ideal Domains

Why Euclidean domains are principal ideal domains and why principal ideal domains have unique factorisation.

Unique Factorization of Polynomials

Unique factorisation in polynomial rings over a field, and the extension to polynomial rings over a UFD.

Unique Factorization of the Integers

The fundamental theorem of arithmetic: existence and uniqueness of prime factorisation, and why the uniqueness half is the difficult one.

Engineering Mathematics13 Aug 2026 · 22 min read

Uniqueness of Reduced Row-Echelon Form

Proof that a matrix has exactly one reduced row-echelon form: pivot columns agree by induction, ranks agree, and rows are forced to coincide entry by entry.

Useful Facts and Standard Estimates

The analytic inequalities, series estimates and elementary bounds relied on repeatedly in the analysis of number-theoretic algorithms.