Engineering

Rational Function Reconstruction

Recovering a rational function from a residue modulo a polynomial, with degree bounds replacing size bounds.

Rational Function Reconstruction in Symbolic Algebra

Using rational function reconstruction inside computer algebra for exact computation over function fields.

Rational Reconstruction

Recovering a rational number from its residue modulo n, the uniqueness conditions, and the role of the extended Euclidean algorithm.

Rational Reconstruction in Symbolic Algebra

Applying rational reconstruction inside computer algebra systems for exact linear solving, interpolation and gcd computation.

Recovering Abelian Group Structure from a Relation Matrix

Recovering the structure and explicit generators of a finite abelian group from a matrix of relations among a generating set.

Engineering Mathematics13 Aug 2026 · 21 min read

Recycling Definitions in Abstract Vector Spaces

How linear combination, span, relations of linear dependence and linear independence transfer unchanged from column vectors to any abstract vector space.

Engineering Mathematics13 Aug 2026 · 19 min read

Reduced Row-Echelon Form

Definition, uniqueness and engineering use of reduced row-echelon form (RREF): leading ones, pivot columns, zero rows and the canonical form of a matrix under row operations.

Reducing the Error Probability

Amplifying the success probability of a randomised algorithm by independent repetition, for one-sided and two-sided error.

Reduction of Indefinite Forms and the Cycle Structure

Reduction of indefinite binary forms, the cycle of reduced forms in each class, and how the cycle encodes the regulator.

Reduction of Positive Definite Binary Forms

Reducing a positive definite binary quadratic form to the unique reduced form in its class, and the resulting class number algorithm.

Regulator and Fundamental Unit Recovery

Extracting fundamental units and the regulator from the kernel of the relation matrix, and confirming the unit system is fundamental.

Relation Matrix Construction

Generating relations among ideal classes, assembling the sparse matrix, and knowing when enough relations have been collected.

Representing Large Integers

Positional representation of multiprecision integers, base selection, sign handling and normalisation invariants.

Engineering Mathematics13 Aug 2026 · 9 min read

Residue Classes and the Ring of Integers Modulo n

The ring Z_n of residue classes, its units and zero divisors, and the condition under which it is a field.

Resultants and Discriminants

The resultant as a criterion for common roots, the discriminant as a test for repeated roots, and how both are computed in practice.

Reversed Formal Laurent Series

Reversed formal Laurent series, the valuation by degree, and their role in rational function reconstruction.

Ring Homomorphisms and Isomorphisms

Ring homomorphisms, kernels as ideals, and the first isomorphism theorem for rings.

Rings: Definitions, Properties and Examples

Commutative rings with unity: axioms, units, and the standard examples used throughout the subject.

Root Finding over Finite Fields

Finding roots of a polynomial in a finite field by GCD with the Frobenius polynomial followed by probabilistic splitting.

Root Finding over the Reals and Complex Numbers

Numerical root finding for polynomials with exact coefficients, root isolation over the reals, and the precision required to be reliable.

Engineering Mathematics13 Aug 2026 · 24 min read

Row Space of a Matrix

The row space of a matrix: definition via the transpose, invariance under row operations, a basis from the non-zero rows of the reduced row-echelon form, and span simplification.

Schoof's Point Counting Algorithm

Schoof's polynomial-time algorithm for counting points on a curve over a finite field, and the SEA improvements.

Schoolbook and Karatsuba Multiplication

Quadratic schoolbook multiplication, the Karatsuba three-multiplication identity, and where the crossover between them sits.

Shanks's Class Group Factoring Method

Shanks's method factoring an integer by finding an ambiguous form in the class group of the corresponding discriminant.

Shanks's Square Forms Factorisation (SQUFOF)

SQUFOF: factoring by finding a square form in the cycle of an indefinite quadratic form, and why it excels for small inputs.

Engineering Mathematics13 Aug 2026 · 22 min read

Similar Matrices

Similar matrices satisfy A = S inverse B S for a non-singular S: definition, a worked similarity transformation, change of basis and the invariants preserved.

Smooth Numbers

Smooth numbers, their density, and why they are the raw material of subexponential factoring and index calculus.

Smoothness and Sub-exponential Complexity

Smooth numbers, the Dickman function, and how balancing smoothness probability against factor base size produces sub-exponential running times.

Solving Linear Congruences

Solving ax = b (mod n): the solvability criterion, the exact number of solutions, and the algorithm via extended Euclid.

Solving Quadratic Congruences

Reducing a general quadratic congruence to a square root extraction, and handling the degenerate cases the reduction assumes away.

Solving Sparse Linear Systems

Iterative methods for large sparse systems over finite fields, and their role as the bottleneck of sieve algorithms.

Solving Systems of Linear Equations

Solving linear systems over a field: consistency, the structure of the solution set, and modular methods for exact rational answers.

Sophie Germain Primes

Sophie Germain primes and safe primes, their use in discrete logarithm cryptography, and the conjectural nature of their density.

Engineering Mathematics13 Aug 2026 · 20 min read

Span of a Set of Vectors

The span of a finite set of column vectors is the set of all their linear combinations; membership testing reduces to deciding consistency of a linear system.

Engineering Mathematics13 Aug 2026 · 25 min read

Spanning Sets in Abstract Vector Spaces

How to construct and verify a spanning set for a subspace of polynomials or matrices: the set equality argument, the consistency test and a worked construction.

Engineering Mathematics13 Aug 2026 · 20 min read

Spanning Sets of Null Spaces

Construct n-r vectors directly from the reduced row-echelon form whose span is exactly the null space of a matrix, using the pattern of ones, zeros and negated entries.

Speeding Up Algorithms via Modular Computation

The modular method for exact computation: bounding the result, computing modulo several primes, and reconstructing.

Speeding Up Polynomial Algorithms via Modular Computation

Applying evaluation homomorphisms and modular reduction to control coefficient and degree growth in polynomial computation.

Splitting Separable Algebras over Finite Fields

Decomposing a finite-dimensional commutative algebra over a finite field into its simple components, generalising polynomial factorisation.

Square Roots Modulo a Prime: the Shanks-Tonelli Algorithm

Extracting square roots modulo a prime: the easy congruence classes, the general Shanks-Tonelli algorithm, and lifting to prime powers.

Square-Free Decomposition of Polynomials

Removing repeated factors using gcds with the derivative, and the characteristic p complication.

Squarefree Factorisation of Polynomials

Separating repeated factors using the derivative, and the modification required in positive characteristic.

Statistical Distance

Statistical distance between distributions, its properties, and its use in proving that a sampler is close to uniform.

Strict Polynomial Time

Strict versus expected polynomial time, and how a Las Vegas algorithm is converted into a bounded-time one.

Engineering Mathematics13 Aug 2026 · 24 min read

Structure and Isomorphism

Isomorphic vector spaces, isomorphisms as structure-preserving invertible linear maps, why isomorphic spaces share dimension, and how to transfer computations.

Structure of the Jacobi Sum Primality Test

The overall design of the Jacobi sum primality test, its two phases, and where its complexity comes from.

Structure of the Unit Group Modulo n

The structure of the multiplicative group of integers modulo n, its decomposition by CRT, and computing element orders.

Sub-exponential Class Group Computation for Quadratic Fields

Sub-exponential class group and regulator computation for quadratic fields by relation collection over a factor base.