Engineering↗
Chinese Remainder Theorem Algorithms
Reconstructing an integer from residues, Garner's incremental method, and CRT as a strategy for controlling coefficient growth.
Content type
Guides
Structured, multi-part guides that take a subject from first principles to applied practice. 3043 pages.
Engineering↗
Chinese Remaindering and Polynomial Interpolation
The Chinese remainder theorem for polynomials, and Lagrange interpolation as its special case.
Engineering↗
Choosing an Algorithm: Decision Guide
A consolidated decision guide across the main computational tasks in this collection.
Engineering↗
Class Group and Unit Computation: the Computational Problem
Why class group and unit computation are a single problem, what the combined algorithm produces, and how the results are verified.
Engineering↗
Class Numbers from Analytic Class Number Formulas
Using L-functions and the analytic class number formula to compute or verify class numbers and regulators.
Engineering↗
Coefficient Explosion in Hermite Normal Form Computation
Why intermediate entries in normal form computation grow so violently, how to recognise it, and the three standard mitigations.
Engineering↗
Column Space of a Nonsingular Matrix
A square matrix is nonsingular exactly when its column space is all of C^n: proof, the right-inverse construction and the cost of a deficient column space.
Engineering↗
Column Space Spanned by Original Columns
Row-reduce, note the pivot columns, then take those columns of the original matrix: a basis for the column space built from genuine columns rather than reduced ones.
Engineering↗
Column Spaces and Systems of Equations
The column space of a matrix is the span of its columns: exactly the set of right-hand sides for which a linear system is consistent, plus the membership test.
Engineering↗
Column Vectors: Equality, Addition and Scalar Multiplication
The vector space of column vectors, with entrywise definitions of equality, addition and scalar multiplication, and how one vector equation replaces a system.
Engineering↗
Complex Arithmetic and Vectors
Conjugation of a column vector entry by entry, and the theorems showing it distributes over vector addition and over scalar multiplication with the scalar conjugated.
Engineering↗
Complex Multiplication and Class Numbers
The link between curves with complex multiplication and class groups of imaginary quadratic orders, and the Hilbert class polynomial.
Engineering↗
Complex Number Arithmetic
Addition, subtraction, multiplication and division of complex numbers, the imaginary unit, reciprocals, and why linear algebra takes its scalars from C.
Engineering↗
Composition of Binary Quadratic Forms
Gauss composition as the group law on form classes, its practical computation, and reduction between compositions.
Engineering↗
Computational Algebraic Number Theory: Field Overview
What computational algebraic number theory actually computes, why the problems are hard, and how the subject's algorithms fit together.
Engineering↗
Computational Number Theory and Algebra: Field Overview
How number theory, abstract algebra and algorithm analysis combine into a single computational discipline, and how the KEVOS Mathematics library is organised.
Engineering↗
Computational Number Theory: Tools and Libraries
Software for computational number theory and algebra, what each is suited to, and how to choose.
Engineering↗
Computing Column Spaces
Four methods for describing the column space of a matrix: raw columns, pivot columns, the transpose-and-reduce route, and expressing the column space as a null space via extende…
Engineering↗
Computing Determinants
Minors, cofactors and expansion about any row or column: how to evaluate a determinant along the sparsest line, and why triangular matrices collapse to a diagonal product.
Engineering↗
Computing Eigenvalues and Eigenvectors
Computing eigenvalues as roots of the characteristic polynomial and eigenvectors as null spaces: the determinant test, eigenspaces and basis extraction.
Engineering↗
Computing Eigenvectors of Linear Transformations
How to compute eigenvalues and eigenvectors of a linear transformation on an abstract vector space: build a matrix representation, solve, then un-coordinatise.
Engineering↗
Computing in the Integers Modulo n
Implementing arithmetic in Z_n: representative choice, reduction after each operation, inversion, and the cost of each primitive.
Engineering↗
Computing Minimal Polynomials in Quotient Algebras
Finding the minimal polynomial of an element of a polynomial quotient algebra by linear algebra on its powers.
Engineering↗
Computing Minimal Polynomials of Sequences
The Berlekamp-Massey algorithm and its Euclidean equivalent for finding the shortest linear recurrence.
Engineering↗
Computing Minimal Polynomials over Finite Fields
Computing the minimal polynomial of a finite field element using conjugates or linear algebra.
Engineering↗
Computing Modular Square Roots: Composite Modulus
Square roots modulo a composite, the four roots for a semiprime, and the equivalence with factoring.
Engineering↗
Computing Modular Square Roots: Prime Modulus
Extracting square roots modulo a prime, the easy case for p congruent to 3 mod 4, and the randomised algorithm in general.
Engineering↗
Computing Modular Square Roots: Prime Power Modulus
Lifting a square root from a prime to a prime power by Hensel's method, and the special handling powers of two require.
Engineering↗
Computing Rank, Kernel and Image
Extracting rank, kernel basis and image basis from an echelon form, and the applications to polynomial factorisation.
Engineering↗
Computing the Inverse of a Matrix
How to compute a matrix inverse: the two-by-two determinant formula, the column-by-column view, and Gauss-Jordan reduction of the augmented array [A | I].
Engineering↗
Computing the Jacobi Symbol
The Euclid-style algorithm for evaluating a Jacobi symbol in quadratic time without factoring either argument.
Engineering↗
Computing the Structure of Residue Rings
The structure of the unit group of a residue ring of the maximal order, and its computation by decomposition and lifting.
Engineering↗
Computing with Elliptic Curves over C
Practical computation with elliptic curves over the complex numbers: periods, the torus map, and heights.
Engineering↗
Conditional Probability and Independence
Conditional probability, Bayes' theorem, independence and the distinction between pairwise and mutual independence.
Engineering↗
Congruences and Modular Arithmetic
Congruence as an equivalence relation compatible with arithmetic, and the basic manipulation rules including where cancellation fails.
Engineering↗
Conjugates of Complex Numbers
The complex conjugate: definition, the theorems that it respects addition and multiplication, involution, conjugate root pairs and its role in adjoints and inner products.
Engineering↗
Conjugates, Norms and Traces
Conjugates of a finite field element, the norm and trace maps, and their surjectivity onto the subfield.
Engineering↗
Consequences of Unique Factorization
What follows from the fundamental theorem: gcd and lcm via exponents, irrationality proofs, divisor counting and multiplicative structure.
Engineering↗
Consistent and Inconsistent Systems
How to decide whether a linear system has a solution: the augmented-column pivot test, the roles of r, D and F, and why a system has zero, one or infinitely many solutions.
Engineering↗
Constructing Tables of Number Fields
Systematically enumerating number fields of small degree and bounded discriminant, with canonical representatives and completeness arguments.
Engineering↗
Continued Fraction Expansion of Real Numbers
Continued fractions, convergents as best rational approximations, and the periodic expansion of quadratic irrationals.
Engineering↗
Cosets and Lagrange's Theorem
Cosets as a partition of a group, Lagrange's theorem, and its consequences for element orders.
Engineering↗
Curve Reduction and Tate's Algorithm
Reduction of an elliptic curve modulo a prime, the classification of bad reduction types, and Tate's algorithm.
Engineering↗
Cyclic and Pure Cubic Field Families
Cyclic cubic and pure cubic fields as parametrised families, with closed-form invariants that avoid general algorithms.
Engineering↗
Cyclic Groups
Cyclic groups, their generators, subgroup structure, and the criterion for the units modulo n to be cyclic.
Engineering↗
Detecting Algebraic and Linear Dependence with LLL
Recovering exact integer relations from numerical approximations using LLL, and the precision requirements that make the method reliable.
Engineering↗
Determinant Computation Strategies
Computing exact determinants by fraction-free elimination, modular methods with Hadamard bounds, and how to choose between them.
Engineering↗
Deterministic Polynomial Factorization Algorithms
Deterministic factorisation over finite fields, the obstacles, and what is known conditionally.