Guides

Deterministic Primality Testing: The Basic Idea

The polynomial identity underlying AKS primality testing and the obstacle that makes it non-trivial to exploit.

Engineering Mathematics13 Aug 2026 · 24 min read

Diagonalization

When a square matrix is similar to a diagonal matrix: the eigenvector basis test, the multiplicity criterion, distinct eigenvalues, and fast matrix powers.

Engineering Mathematics13 Aug 2026 · 25 min read

Dimension

Dimension of a vector space defined as the size of any basis, with the spanning-sets theorem and the proof that all bases of a space have identical size.

Engineering Mathematics13 Aug 2026 · 25 min read

Dimension of Common Vector Spaces

Dimensions of the standard vector spaces: column vectors, polynomials of bounded degree and matrices, plus subspace dimension and infinite-dimensional examples.

Discrete Logarithms in Groups of Prime Power Order

Solving discrete logarithms in a group of prime power order by digit-by-digit lifting.

Discrete Logarithms in the Full Group Modulo p

The Pohlig-Hellman reduction combining prime power subproblems by the Chinese remainder theorem.

Discriminants and Integral Bases

The discriminant of a basis, the field discriminant, and the index-squared relation that governs maximal order computation.

Distinct Degree Factorisation

Separating irreducible factors by degree using GCDs against Frobenius powers, and the early-abort strategies that make it fast.

Distinct Degree Factorization

Separating the irreducible factors of a polynomial by degree using gcds with Frobenius powers.

Engineering Mathematics13 Aug 2026 · 9 min read

Divisibility and Primality

Divisibility of integers, the definition of primes and composites, and the basic properties that support every later result in elementary number theory.

Division with Remainder for Integers

The division algorithm for integers, the uniqueness of quotient and remainder, and the role of well-ordering in establishing it.

ECM Stage Two and Practical Tuning

ECM stage two, the large prime search, and how the two bounds are tuned together.

Engineering Mathematics13 Aug 2026 · 23 min read

Eigenvalues and Eigenvectors of a Matrix

Definition of eigenvalues and eigenvectors, why the eigenvector must be non-zero while the eigenvalue may be zero, and how eigenvectors for one eigenvalue form a subspace.

Eigenvalues and Eigenvectors of Linear Transformations

Eigenvalues and eigenvectors of a linear transformation of a vector space to itself: eigenspaces, the meaning of zero, and the link to matrix representations.

Eigenvalues of Hermitian Matrices

Hermitian and real symmetric matrices have real eigenvalues and orthogonal eigenvectors: inner-product proofs, orthonormal modal bases and engineering use.

Engineering Mathematics13 Aug 2026 · 24 min read

Elementary Row Operations and Row Equivalence

The three elementary row operations, their shorthand notation, why each is reversible, and how row equivalence groups matrices with identical solution sets.

Elliptic Curve Arithmetic Modulo N

Implementing curve arithmetic over a composite modulus: coordinate systems, inversion handling, and Montgomery form.

Elliptic Curves Modulo N

Working with elliptic curves modulo a composite, why the group law fails, and why that failure is exactly what is wanted.

Elliptic Curves: Basic Definitions

What an elliptic curve is, why the group structure exists, and the three distinct roles curves play in this collection.

Elliptic Integrals and Elliptic Functions

The analytic origin of elliptic curves in elliptic integrals, and the doubly periodic functions that invert them.

Equal Degree Factorization

Splitting a product of same-degree irreducible factors by random splitting, and the success probability.

Equivalent Systems and Equation Operations

Two systems are equivalent when their solution sets agree. The three equation operations, the theorem that they preserve solutions, and why the scalar must be non-zero.

Error-Correcting Codes and Algebraic Decoding

Reed-Solomon codes, their distance property, and decoding by rational function reconstruction.

Essential Discriminant Divisors

Primes that divide the index for every choice of defining polynomial, why they exist, and what they force computationally.

Euclid's Algorithm for Integer GCD

Euclid's algorithm for greatest common divisors, its correctness, and the Fibonacci worst case that bounds its iteration count.

Euclid's Algorithm for Polynomials

The Euclidean algorithm for polynomial gcds, its degree-based termination, and coefficient growth over the rationals.

Euler's Phi Function

Euler's totient function: its definition, multiplicativity, closed form from the prime factorisation, and computational status.

Engineering Mathematics13 Aug 2026 · 25 min read

Examples of Vector Spaces

A catalogue of vector spaces: column vectors, matrices, polynomials, infinite sequences, functions and the trivial space, plus non-examples that fail closure.

Engineering Mathematics13 Aug 2026 · 23 min read

Existence of Eigenvalues and Eigenvectors

Every square matrix has at least one eigenvalue: the determinant-free proof using a Krylov sequence, an annihilating polynomial and its linear factors over the complex field.

Expectation and Variance

Expectation, variance, their algebraic properties and their use in analysing randomised algorithms.

Explicit Estimates for Prime Counting

Effective, fully explicit bounds on the prime counting function and the nth prime, usable directly in algorithm analysis.

Extended Echelon Form

Extended echelon form: augmenting a matrix with an identity block and reducing to obtain the submatrices B, C, J, K and L, their properties, and the generalised inverse relation…

Factor Base Selection and Smoothness

Choosing the factor base for class group computation, the smoothness trade-off, and how base size interacts with the linear algebra.

Factoring and Computing Euler's Phi Function

The polynomial-time equivalence between factoring a modulus, computing phi, and recovering an RSA private exponent.

Factoring Polynomials over Algebraic Number Fields

Factoring polynomials whose coefficients lie in a number field, by reduction to the rational case via norms.

Factoring Polynomials over the Integers

The modular-lift-recombine pipeline, the exponential recombination problem, and the LLL-based algorithm that makes factorisation polynomial time.

Faster Integer Arithmetic: Karatsuba and Beyond

Karatsuba multiplication and the divide-and-conquer family that reduces the exponent below two.

Faster Polynomial Arithmetic

Subquadratic polynomial multiplication by Karatsuba and FFT methods, and the crossover behaviour.

Faster Square-Free Decomposition

Yun's algorithm and other improvements to squarefree decomposition, and their cost advantages.

Fermat and Strong Pseudoprime Tests

The Fermat test, its failure on Carmichael numbers, and the strong pseudoprime test that repairs it.

Fermat's Little Theorem and Euler's Theorem

Fermat's little theorem, Euler's generalisation, and their role as the foundation of primality testing and public-key cryptography.

Field Isomorphism and the Normal Closure

Testing whether two number fields are isomorphic, computing the isomorphisms, and constructing the normal closure.

Finding a Generator of the Group of Units Modulo p

Locating a generator of Z_p*, the test based on the factorisation of p-1, and the density of generators.

Finding Primitive Roots and Generators

Locating a generator of a cyclic group, why the search is easy but verification requires a factorisation, and the deterministic gap.

Finding Short Vectors in Lattices

Enumeration and reduction-based methods for finding short lattice vectors, and where the exact shortest vector is genuinely needed.

Finite Field Arithmetic in Practice

Selecting representations and algorithms for real finite field workloads, with the operation mixes that arise in factoring, decomposition and point counting.

Finite Field Element Representation

Representing elements of a finite field as polynomials modulo an irreducible, choosing the modulus, and the trade-offs against logarithmic and normal bases.

Finite Field Multiplication and Inversion

Multiplication with reduction, inversion by extended Euclid or by exponentiation, and the Itoh-Tsujii method for extension fields.