Tag
Factoring
16 resources tagged “Factoring” across the knowledge library.
16 items
Article7 Aug 2026Computational Algebraic Number Theory: Field OverviewWhat computational algebraic number theory actually computes, why the problems are hard, and how the subject's algorithms fit together.4 min readRead MoreArticle7 Aug 2026Primality Versus Factoring: Framing the ProblemsWhy proving compositeness is easy, proving primality is harder, and factoring is harder still — and what this asymmetry means in practice.2 min readRead MoreArticle7 Aug 2026Shanks's Class Group Factoring MethodShanks's method factoring an integer by finding an ambiguous form in the class group of the corresponding discriminant.2 min readRead MoreArticle7 Aug 2026Shanks'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.2 min readRead MoreArticle7 Aug 2026The Elliptic Curve Method: Stage OneECM stage one: multiplying a point by a highly smooth scalar to reach the identity in one component.2 min readRead MoreArticle7 Aug 2026The Pollard Rho Factoring MethodPollard's rho method: cycle detection in a pseudorandom sequence, the birthday bound, and Brent's improvement.2 min readRead MoreArticle7 Aug 2026The Schnorr-Lenstra Class Group Factoring MethodFactoring via class groups of quadratic orders, and its place as the conceptual bridge to the elliptic curve method.2 min readRead MoreArticle7 Aug 2026Trial Division and Lehman's MethodTrial division as the first factoring step, its cost, and Lehman's improvement on Fermat's method.2 min readRead MoreGuide6 Aug 2026Classical Factoring: Trial Division, Fermat and LehmanTrial division and wheel factorisation, Fermat's difference of squares method, Lehman's improvement, and the role of these methods as a preprocessing stage.5 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 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 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 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 MoreGuide6 Aug 2026The Number Field SieveThe number field sieve: polynomial selection, sieving over two sides, the algebraic factor base and character columns, the square root step in a number field, and the special number field sieve.5 min readRead MoreGuide6 Aug 2026The Quadratic Sieve and MPQSThe quadratic sieve, sieving by roots of a polynomial, the multiple polynomial variation, large prime variations, and the linear algebra stage.4 min readRead More