Modern Factoring Methods
Elliptic Curves Modulo N
Working with elliptic curves modulo a composite, why the group law fails, and why that failure is exactly what is wanted.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0668
An elliptic curve modulo a composite is not a group, because inversion can fail. That failure is not a defect to be worked around — it is the mechanism by which factors are found.
The Chinese remainder picture
By the Chinese remainder theorem, the points modulo a composite correspond to pairs of points modulo each prime factor. Arithmetic proceeds independently in each component.
Where the failure occurs
The addition formulas require inverting a difference of coordinates. Modulo a composite that inverse may not exist, and the extended Euclidean algorithm returns a non-trivial GCD instead.
Detecting a factor during curve arithmetic
- Attempt an inversionDuring point addition or doubling.
- Run extended EuclidAgainst the modulus.
- Check the GCDIf it is one, invert normally.
- If it is the modulusBoth components hit the identity together; no information, restart.
- If it is betweenA proper factor has been found.
Why this beats p-1
| Method | Auxiliary group | Order |
|---|---|---|
| Pollard p-1 | Multiplicative group modulo p | Fixed at p minus one |
| ECM | Elliptic curve group modulo p | Varies with the curve, within the Hasse interval |
The Hasse interval
Curve orders are spread across an interval of width roughly four times the square root of the prime. A random curve's order behaves, for smoothness purposes, like a random integer in that interval.
Curve selection
Curves are chosen by a construction guaranteeing a point is known without requiring a square root, and preferably biasing the order toward divisibility by small numbers — see stage one.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.3.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.