Engineering

Testing and Constructing Irreducible Polynomials

Testing irreducibility over a finite field and constructing irreducible polynomials of prescribed degree.

Testing Quadratic Residuosity: Prime Modulus

Deciding quadratic residuosity modulo a prime, and why the problem is easy in this case.

Testing Quadratic Residuosity: Prime Power and Composite Modulus

Quadratic residuosity modulo prime powers and composites, the reduction by Chinese remaindering, and where the hardness enters.

Engineering Mathematics13 Aug 2026 · 21 min read

Testing Subspaces

The three-condition subspace test: non-empty, closed under addition, closed under scalar multiplication. Proof, worked verifications and the standard counterexamples.

The AKS Algorithm and Its Analysis

The AKS algorithm in full, its correctness argument, complexity, and why it is not used in practice.

The Algebra of Linear Transformations

The endomorphism algebra of a vector space, minimal and characteristic polynomials, and the module view of a linear operator.

The Baby Step/Giant Step Method

Shanks' baby step giant step algorithm, its square-root running time, and the time-memory trade-off it embodies.

The Baillie-PSW Compositeness Test

The Baillie-PSW test combining a strong base-two test with a strong Lucas test, and its status as the practical standard.

The Berlekamp Factorisation Algorithm

Berlekamp's linear algebra approach to factoring over a finite field, the Berlekamp subalgebra, and when it outperforms the GCD pipeline.

The Birthday Paradox

The birthday problem, the square-root threshold for collisions, and its algorithmic consequences.

The Buchmann-Lenstra Prime Decomposition Method

Decomposing any prime, including those dividing the index, by splitting the algebra of the order modulo that prime.

Engineering Mathematics13 Aug 2026 · 22 min read

The Change-of-Basis Matrix

The change-of-basis matrix converts coordinates from one basis to another, is the representation of the identity transformation, and is always non-singular.

The Characteristic Polynomial and the Hessenberg Method

Computing the characteristic polynomial via Hessenberg reduction, and its role in producing minimal polynomials of algebraic numbers.

The Chinese Remainder Theorem

The Chinese remainder theorem as a ring isomorphism, its constructive proof, and its role in decomposing modular computation.

The Conjugate Vector Representation

Representing a field element by its images under all embeddings, the analytic information this exposes, and the precision it demands.

The Continued Fraction Factorisation Method

CFRAC: generating small quadratic residues from the continued fraction expansion, and the congruence-of-squares framework it established.

The Coordinatization Principle

The coordinatization principle: questions about linear combinations, independence and spanning in an abstract vector space can be answered in complex n-space.

The Dedekind Criterion for p-Maximality

A cheap modular test deciding whether an order is maximal at a given prime, without computing the maximal order.

Engineering Mathematics13 Aug 2026 · 22 min read

The Determinant of a Matrix

The recursive definition of the determinant via submatrices, the 2x2 formula ad - bc, notation and cost, and why a single scalar decides whether a square matrix is singular.

The Diffie-Hellman Key Establishment Protocol

Diffie-Hellman key agreement, the assumptions it rests on, and the authentication gap that makes it vulnerable alone.

The Dirichlet Unit Theorem, Computationally

The structure of the unit group, its rank from the signature, and what computing units actually requires.

The Elliptic Curve Method: Stage One

ECM stage one: multiplying a point by a highly smooth scalar to reach the identity in one component.

The Error Term in the Prime Number Theorem

How closely li(x) approximates pi(x), the connection to zeta zeros, and what the Riemann hypothesis would give.

The Euclidean Algorithm: Classical and Binary Variants

The classical Euclidean algorithm, the binary variant that replaces division with shifts, and how to choose between them.

The Existence of Finite Fields

Construction of a field of any prime power order, and the proof that one exists for every such order.

The Extended Euclidean Algorithm

Computing Bezout coefficients alongside the gcd, the recurrence for the coefficient sequences, and the size bounds that make it practical.

The Extended Euclidean Algorithm and Bezout Coefficients

Computing Bezout coefficients alongside the GCD, modular inversion as its principal application, and controlling coefficient growth.

The Fermat Test and Carmichael Numbers

The Fermat primality test, pseudoprimes, and the Carmichael numbers that defeat it for every base.

The Field of Fractions of an Integral Domain

Constructing the field of fractions of an integral domain, its universal property, and the standard examples.

Engineering Mathematics13 Aug 2026 · 9 min read

The Four Core Computational Tasks of Number Fields

The four fundamental computational problems for a number field, their dependencies, and what counts as a complete answer to each.

The Four Fundamental Subsets of a Matrix

The null space, row space, column space and left null space of a matrix, all obtained from the two submatrices C and L of one extended echelon form reduction.

The Frobenius Map

The Frobenius endomorphism, its fixed field, its order, and the Galois structure of finite field extensions.

The Fundamental Unit of a Real Quadratic Field

Computing the fundamental unit of a real quadratic field by continued fractions, its connection to the Pell equation, and its size.

The Galois Group Computation Problem

What computing a Galois group means, why the splitting field cannot be constructed, and the transitive group classification that makes the problem finite.

The Goldilocks Theorem: Size, Independence and Spanning

With the dimension known, a candidate set that is too large is dependent, one too small cannot span, and one of the right size needs only a single check.

The Goldwasser-Kilian Primality Test

Primality proving by elliptic curves with known point counts, its recursive certificate, and the point-counting bottleneck.

The Gram-Schmidt Orthogonalisation Procedure

Gram-Schmidt orthogonalisation, the coefficients that drive lattice reduction, and why the orthogonal vectors themselves are not lattice vectors.

The Gram-Schmidt Procedure

Gram-Schmidt converts a linearly independent set into an orthogonal set with the same span by successive projections, and it yields the QR factorisation.

The Group Law on an Elliptic Curve

The chord-and-tangent addition law, its explicit formulas, and the coordinate systems that avoid inversion.

The Hermite Normal Form Algorithm

The Hermite normal form, the classical column-reduction algorithm, and the modular variant that bounds entry growth.

The Ideal Class Group

The class group as the obstruction to unique factorisation, its finiteness, and what a complete computation must produce.

Engineering Mathematics13 Aug 2026 · 22 min read

The Inverse of a Matrix

Definition of the matrix inverse: the two-sided condition AB = BA = I, why only square matrices qualify, uniqueness, and how the inverse solves Ax = b.

The Inverse of a Matrix

Matrix inversion over a field, its computation by elimination, and why explicit inversion is usually the wrong operation.

The Jacobi Symbol

The Jacobi symbol as the multiplicative extension of the Legendre symbol to odd composite moduli, and what it does and does not tell you.

The Law of Quadratic Reciprocity

The law of quadratic reciprocity, its statement, and why it makes symbol evaluation efficient.

Engineering Mathematics13 Aug 2026 · 23 min read

The Left Null Space

The left null space of a matrix: definition as the null space of the transpose, its interpretation as recorded row operations, dimension m minus rank, and use in redundancy anal…

The Legendre Symbol

The Legendre symbol as a multiplicative character, its evaluation by Euler's criterion, and the supplementary laws.