Modern Factoring Methods
Elliptic Curve Arithmetic Modulo N
Implementing curve arithmetic over a composite modulus: coordinate systems, inversion handling, and Montgomery form.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0669
The inner loop of ECM is scalar multiplication on a curve modulo a composite. Since inversions are both expensive and the source of the answer, how they are handled determines both speed and correctness.
The inversion dilemma
Coordinate systems
| System | Inversions | Cost per doubling |
|---|---|---|
| Affine | One per operation | Fewest multiplications |
| Projective | None | More multiplications |
| Montgomery form | None | Very efficient; ideal for scalar multiplication |
Montgomery form
Montgomery curves admit a scalar multiplication using only the first coordinate, via a ladder that performs one doubling and one differential addition per bit.
The identity check
In projective coordinates a point is the identity exactly when its final coordinate is zero modulo the relevant prime. Taking the GCD of that coordinate with the modulus is the factor test.
Detecting a factor without inversions
- Run the scalar multiplicationEntirely in projective coordinates; no inversions.
- Take the GCDOf the final coordinate with the modulus.
- InterpretOne means no factor; the modulus means restart; anything else is a factor.
Curve and point generation
Batching
Modular arithmetic
Every operation is a modular multiplication, so that is where the time goes. Montgomery reduction is standard, and for a fixed modulus used across millions of operations the setup cost is entirely amortised.
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.