Engineering

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.

Hash Tables

Hash tables analysed with universal families: expected chain length, load factor and collision resolution.

Hensel Lifting for Polynomial Factors

Lifting a factorisation modulo a prime to a factorisation modulo a prime power, the quadratic variant, and the coprimality condition.

Engineering Mathematics13 Aug 2026 · 21 min read

Homogeneous Systems of Equations

Linear systems with every constant term zero: why they are always consistent, what the trivial solution is, and why more unknowns than equations guarantees infinitely many solut…