Tag
Computational Number Theory
58 resources tagged “Computational Number Theory” across the knowledge library.
58 items · page 2 of 3
Guide6 Aug 2026Integer Square Roots and Perfect Power DetectionComputing exact integer square roots by Newton's method, fast rejection of non-squares by modular filters, and detection of perfect powers and prime powers.5 min readRead MoreGuide6 Aug 2026Lattices and Quadratic FormsLattices as discrete subgroups, bases and unimodular change of basis, the Gram matrix and determinant, successive minima, and the correspondence with positive definite quadratic forms.4 min readRead MoreGuide6 Aug 2026Legendre, Jacobi and Kronecker SymbolsQuadratic residues, Euler's criterion, the Legendre symbol, its Jacobi and Kronecker extensions, and the reciprocity-based algorithm that evaluates them in logarithmic time.4 min readRead MoreGuide6 Aug 2026Linear Algebra Algorithms over Fields and RingsExact Gaussian elimination, fraction-free elimination, determinant and characteristic polynomial algorithms, and kernel and image computation over fields and over ℤ.5 min readRead MoreGuide6 Aug 2026Modular Exponentiation and Powering AlgorithmsLeft-to-right and right-to-left binary powering, sliding window exponentiation, addition chains, and the generic monoid formulation that makes one routine serve many algebraic structures.6 min readRead MoreGuide6 Aug 2026Multiprecision Integer ArithmeticRepresentation of multiprecision integers, schoolbook and fast multiplication, division, modular reduction strategies, and how to choose the right base ring for a computation.6 min readRead MoreGuide6 Aug 2026Numerical Tables: KEVOS Sourcing PolicyThe KEVOS two-layer knowledge architecture applied to number theory: durable method in the vault, numeric catalogue data sourced from current authoritative databases such as LMFDB and PARI.5 min readRead MoreGuide6 Aug 2026Orders and Ideals in Number FieldsOrders, the maximal order, fractional and integral ideals, unique factorisation of ideals in a Dedekind domain, ideal arithmetic by Hermite normal form, and the two-element representation.4 min readRead MoreGuide6 Aug 2026Pollard's p−1 Method and Its RelativesThe p−1 method with its two stages, smoothness assumptions, the p+1 method using Lucas sequences, and the implications for choosing cryptographic primes.4 min readRead MoreGuide6 Aug 2026Pollard's Rho Factoring MethodPollard's rho method: iteration and cycle structure, Floyd and Brent cycle detection, the birthday bound, batching of GCDs, and Pollard's rho for discrete logarithms.4 min readRead MoreGuide6 Aug 2026Polynomial Arithmetic and GCD in Unique Factorisation DomainsDense and sparse polynomial representation, multiplication algorithms, pseudo-division over a UFD, primitive parts and content, and the subresultant and modular remedies for coefficient growth.4 min readRead MoreGuide6 Aug 2026Primality Testing versus FactoringThe separation between primality testing and factoring, compositeness tests versus primality proofs, probable primes, pseudoprimes, and how to select a testing strategy.5 min readRead MoreGuide6 Aug 2026Prime Decomposition: the Buchmann–Lenstra MethodPrime decomposition for primes dividing the index: Newton polygons, splitting separable algebras over F_p, ideal arithmetic modulo p, and the Buchmann-Lenstra algorithm.5 min readRead MoreGuide6 Aug 2026Quadratic Fields and Binary Quadratic FormsQuadratic fields, their discriminants and integral bases, prime decomposition by the Kronecker symbol, binary quadratic forms, reduction, and the correspondence between form classes and ideal classes.5 min readRead MoreGuide6 Aug 2026Real Quadratic Fields and the Infrastructure MethodRegulators and fundamental units of real quadratic fields, the continued fraction algorithm, the exponential cost problem, and Shanks's infrastructure with the distance function.5 min readRead MoreGuide6 Aug 2026Representing Algebraic NumbersThe standard, matrix, conjugate-vector and minimal-polynomial representations of an algebraic number, their relative costs, and how to convert between them.4 min readRead MoreGuide6 Aug 2026Root Finding over the Complex NumbersNumerical root finding for polynomials over C: conditioning, the Newton and Aberth methods, splitting-circle approaches, and the precision management needed to support exact number field computations.4 min readRead MoreGuide6 Aug 2026Shanks's SQUFOF Factoring MethodThe SQUFOF algorithm: continued fraction expansion of the square root, square forms, the reverse cycle, multipliers, and why it excels in a narrow but important range.4 min readRead MoreGuide6 Aug 2026Software Packages for Computational Number TheoryA practical guide to computer algebra systems and libraries for algebraic number theory: PARI/GP, Sage, Magma, FLINT, GMP and NTL, with selection guidance and verification practice.4 min readRead MoreGuide6 Aug 2026Solving Polynomial Equations Modulo pRoot-finding modulo a prime: the gcd with x^p − x, equal-degree splitting by random shifts, and the special low-degree cases that admit closed forms.4 min readRead MoreGuide6 Aug 2026Square Roots Modulo a PrimeComputing modular square roots: the p ≡ 3 (mod 4) shortcut, the Tonelli–Shanks algorithm and its 2-adic structure, and Cornacchia's algorithm for x² + dy² = p.4 min readRead MoreGuide6 Aug 2026The Cohen–Lenstra HeuristicsThe Cohen-Lenstra heuristics for class groups of quadratic fields, the weighting principle, predicted divisibility frequencies, and their role in validating computations.4 min readRead MoreGuide6 Aug 2026The Continued Fraction Factoring MethodCFRAC: generating small residues from the continued fraction expansion of the square root, smoothness testing, the linear algebra step, and its historical role as precursor to the sieves.4 min readRead MoreGuide6 Aug 2026The Elliptic Curve Method (ECM)Lenstra's elliptic curve factoring method: curves modulo a composite, the failed inversion that reveals a factor, stage one and stage two, curve parameterisations, and the role of ECM in practice.5 min readRead More