Programming Praxis

We recently examined an improved second stage for John Pollard’s p−1 factoring algorithm. In today’s exercise we will look at the similar second stage for the elliptic curve factoring algorithm, an optimization known as the improved standard continuation. We will be following Algorithm 7.4.4 in the book Prime Numbers: A Computational Perspective by Richard Crandall and Carl Pomerance.

Recall from our previous exercises that the first stage of the elliptic curve algorithm ends with a point Q that fails to find a factor. In the second stage we want to calculate elliptic multiples of Q: 2Q, 4Q, 6Q, and so on. Recall also that the p−1 method uses a strength reduction technique to replace exponentiation with multiplication. The improved standard continuation uses a similar technique to reduce elliptic multiplication, which is slow, to two modular multiplications plus an occasional elliptic addition. Here is the algorithm as given by Crandall and Pomerance:

S₁ = doubleh(Q)
S₂ = doubleh(S₁)
for (d ∈ [1,D]) { // this loop computes S_d = [2d]Q
    if (d > 2) S_d = addh(S_d−1, S₁, S_d−2)
    β_d = X(S_d) Z(S_d) (mod n)
}
g = 1
B = B₁ − 1 // B is odd
T = [B − 2D]Q // via Algorithm 7.2.7
R = B[Q] // via Algorithm 7.2.7
for (r = B; r < B₂; r = r + 2D) {
    α = X(R) Z(R) mod n
    for (prime q ∈ [r + 2, r + 2D]) { // loop over primes
        δ = (q − r) / 2 // distance to next prime
        g = g((X[R] − X(S_δ))(Z(R) + Z(S_δ)) − α + β_δ) mod n
    }
    (R, T) = (addh(R, S_D, T), R)
}
g = gcd(g, n)
if (1 < g < n) return g // found a nontrivial factor of n

In the notation of Crandall and Pomerance, B₁ is the first-stage bound and B₂ is the second-stage bound. D is a parameter that mediates a time-space trade-off, with a larger D taking more space but running faster; the memory required is about 3D n-sized integers. Q, R and T are points on the elliptic curve; the coordinates of point P are X(P) and Z(P). S[1 .. D] is an array of elliptic points, and β[1 .. D] stores the products of the X and Z coordinates of the elliptic points in S.

The S array corresponds to the array that we used in the second stage of the p−1 algorithm, and is built at runtime in a similar way in the first loop (on d) of the algorithm given above. Then the primes from B₁ to B₂ are processed in segments of size 2D, with r the base value of each segment and R the corresponding elliptic point. At each prime in the segment the difference to the base of the segment is calculated, then the stored values of S_δ and β_δ are used to update the product g. When all the primes have been calculated, a single gcd is calculated; if it is nontrivial, it is reported, otherwise the curve has failed to find a factor and a different curve must be tried.

The long formula that updates g takes the place of the elliptic multiplications of the first stage, in a very clever way. If you have available points R and S[1 .. D], the elliptic multiplication [s]Q = [r + δ]Q = O can be tested by checking whether the cross product X_r Z_δ − X_δ Z_r has a nontrivial gcd with n; simple algebra can reduce the work of computing the cross product even further with the formula shown in the algorithm.

Thus, by storing precomputed values of X_δ, Z_δ and the product X_δ Z_δ, it is possible to loop through the primes from B₁ to B₂ with only two modular multiplications per prime, plus a single elliptical addition for each segment.

Your task is to write a function to compute factors using the improved standard continuation of the elliptic curve factorization method. 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 3