Programming Praxis

We discussed Hendrik Lenstra’s algorithm for factoring integers using elliptic curves in three previous exercises. After Lenstra published his algorithm in 1987, mathematicians studied the algorithm extensively and made many improvements. In this exercise, and the next, we will study a two-stage version of elliptic curve factorization that features improved elliptic arithmetic and is much faster than Lenstra’s original algorithm. Today’s exercise looks at the improved elliptic arithmetic; we will look at the two-stage algorithm in the next exercise.

If you look at Lenstra’s original algorithm, much of the time is spent calculating modular inverses. Peter Montgomery worked out a way to eliminate the modular inverses by changing the elliptic arithmetic; instead of using the curve y² = x³ + ax + b, Montgomery uses the curve y² = x³ + ax² + x. Additionally, he does a co-ordinate transform to eliminate the y variable, so we don’t need to figure out which of the quadratic roots to follow. Finally, Montgomery stores the numerator and denominator of the a parameter separately, eliminating the modular inverse. We won’t give more of the math; for those who are interested, a good reference is Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance.

Here are the elliptic addition, doubling and multiplication rules for Montgomery’s elliptic curves:

A curve is given by the formula y² = x³ + (A_n / A_d – 2)x² + x (mod n).

A point is stored as a two-tuple containing its x and z co-ordinates.

To add two points P₁(x₁,z₁) and P₂(x₂,z₂), given the point P₀(x₀,z0) = P₁ – P₂ (notice that the curve is not used in the calculation):

x = ((x₁–z₁) × (x₂+z₂) + (x₁+z₁) × (x₂–z₂))² × z₀ mod n
z = ((x₁–z₁) × (x₂+z₂) – (x₁+z₁) × (x₂–z₂))² × x₀ mod n

To double the point P:

x = (x+z)² × (x–z)² × 4 × Ad mod n
z = (4 × Ad × (x–z)² + t × An) × t mod n where t = (x+z)² – (x–z)²

Multiplication is done by an adding/doubling ladder, similar to the method used in the Lucas chain in the exercise on the Baillie-Wagstaff primality checker; the Lucas chain is needed so that we always have the point P₁–P₂. For instance, the product 13P is done by the following ladder:

2P = double(P)
3P = add(2P, P, P)
4P = double(2P)
6P = double(3P)
7P = add(4P, 3P, P)
13P = add(7P, 6P, P)

Richard Brent gave a method to find a suitable elliptic curve and a point on the curve given an initial seed s on the half-open range [6, n), with all operations done modulo n:

u = s² – 5
v = 4s

A_n = (v–u)³ (3u+v)
A_d = 4u³v

P = (u³, v³)

Your task today is to write the three functions that add, double, and multiply points on an elliptic curve and the function that finds a curve and a point on the curve; the payoff will be in the next exercise that presents elliptic curve factorization. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2