Engineering Mathematics

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.

Engineering Mathematics13 Aug 2026 · 22 min read

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.

Finite Fields: Preliminaries

The characteristic of a finite field, why its order is a prime power, and the prime subfield.

Finite Probability Distributions

Finite sample spaces, probability distributions, events and the basic laws governing them.

Flipping a Coin Until a Head Appears

The geometric waiting time, its expectation and tail, and its role as the model for repeat-until-success algorithms.

Formal Derivatives of Polynomials

The formal derivative as an algebraic operation, its rules, and its use in detecting repeated factors.

Formal Laurent Series

Formal Laurent series, the field of fractions of the power series ring, and the valuation structure.

Formal Power Series

Formal power series, their arithmetic, invertibility criterion, and use as generating functions.

Galois Groups of Cubic and Quartic Fields

Complete determination of Galois groups in degrees three and four, where the discriminant and one cubic resolvent decide everything.

Galois Groups of Quintic Fields

Determining Galois groups in degree five, where solvability by radicals first fails and the resolvent degrees grow.

Galois Groups of Sextic and Septic Fields

Degrees six and seven, where the number of candidate groups and the resolvent degrees make careful strategy essential.

Gauss Sums and Jacobi Sums

Characters, Gauss sums and Jacobi sums, and the properties that make them useful for primality testing.

Gaussian Elimination

Gaussian elimination over a field, its complexity, pivoting, and its role as the bottleneck in sieve algorithms.

Gaussian Elimination and Linear Systems

Exact Gaussian elimination, pivoting for entry growth rather than stability, and the fraction-free Bareiss variant.

Gaussian Elimination over Finite Fields

Elimination over a finite field, structured methods for very large sparse systems, and why the linear algebra stage limits sieving methods.

General Properties of Extension Fields

Field extensions, degree, algebraic elements and minimal polynomials.

Generating a Random Factored Number

Producing a uniformly random integer together with its complete factorisation, in polynomial time, without factoring.

Generating a Random k-Bit Prime

Generating a prime of exactly k bits, the density in that range, and the constraints imposed by cryptographic use.

Generating a Random k-Bit Prime with Miller-Rabin

Assembling bit-length constraint, trial division filtering and Miller-Rabin into a complete prime generator.

Generating a Random Non-Increasing Sequence

Sampling a random non-increasing sequence in a bounded range, and its role as a subroutine in generating factored numbers.

Generating a Random Number from a Given Interval

Sampling uniformly from an arbitrary range using a source of random bits, and controlling the resulting bias.

Generating a Random Prime

Generating a random prime by repeated candidate testing, the expected number of trials, and the sieving optimisation.

Generating a Random Prime Between 2 and M

Generating a uniform random prime below a bound, the analysis of the retry loop, and the resulting output distribution.

Group Homomorphisms and Isomorphisms

Structure-preserving maps between groups, isomorphisms, and what it means for two groups to be the same.

Hash Function Families

Families of hash functions, keyed selection, and the properties required of them in algorithm design.