Modern Factoring Methods
The Schnorr-Lenstra Class Group Factoring Method
Factoring via class groups of quadratic orders, and its place as the conceptual bridge to the elliptic curve method.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0667
The Schnorr-Lenstra method factors by computing in the class group of a quadratic order attached to the target. Its importance is conceptual: it made explicit the idea of an auxiliary group whose order can be varied.
The idea
Choose a discriminant involving the target and a multiplier. If the class number of that discriminant is smooth, the group structure can be exploited to produce an ambiguous form, which factors the discriminant.
The algorithm
Schnorr-Lenstra class group factoring
- Choose a multiplierForming a discriminant from the target.
- Work in the class groupUsing composition and reduction.
- Raise to a smooth exponentThe product of prime powers below a bound, as in p-1.
- Look for an ambiguous formOne equal to its own inverse.
- Extract the factorAn ambiguous form gives a factorisation — see Shanks's method.
- RetryWith a different multiplier if unsuccessful.
The complexity
Why ECM superseded it
| Aspect | Class group method | ECM |
|---|---|---|
| Auxiliary group | Class group of a quadratic order | Elliptic curve group modulo n |
| Group order varies | With the multiplier | With the curve |
| Order size | Roughly the square root of the target | Roughly the size of the unknown prime factor |
| Arithmetic cost | Composition and reduction — expensive | A few modular multiplications |
| Depends on | The size of the target | The size of the factor |
The conceptual line
Each step generalises the auxiliary group and gains flexibility. ECM is the end of the line for this idea, and the sieves take an entirely different route — see elliptic curves modulo N.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.2. 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.