Classical Primality and Factoring
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.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0655
Shanks's class group method factors an integer by working in the class group of a quadratic order whose discriminant involves that integer. An ambiguous form in that group reveals a factorisation.
The connection
Ambiguous forms — those equal to their own inverse — correspond to factorisations of the discriminant. Finding one therefore factors the number.
The method
Shanks's class group factoring method
- Choose a discriminantInvolving the number to be factored, typically a small multiple of it.
- Compute the class numberOr its order structure — see class numbers by forms.
- Find a two-torsion elementRaise a random form to the odd part of the class number.
- Read the factorisationAn ambiguous form gives a factor of the discriminant.
Computing the class number
The class number is found by a baby-step giant-step search in the class group, using the analytic class number formula to estimate its size and narrow the search.
Why it matters
Genus theory
The two-torsion of the class group is described by genus theory in terms of the prime divisors of the discriminant. This makes the correspondence between ambiguous forms and factorisations completely explicit, and it is why the method is guaranteed to work rather than merely likely to.
Relation to SQUFOF
Shanks also developed SQUFOF, which finds a square form during cycle traversal in the indefinite case. SQUFOF has the same asymptotic cost but far smaller constants and negligible memory, making it genuinely practical for small numbers.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.5.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.