Improved Standard Continuation

November 8, 2011

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:

S1 = doubleh(Q)
S2 = doubleh(S1)
for (d ∈ [1,D]) { // this loop computes Sd = [2d]Q
    if (d > 2) Sd = addh(Sd−1, S1, Sd−2)
    βd = X(Sd) Z(Sd) (mod n)
}
g = 1
B = B1 − 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 < B2; r = r + 2D) {
    α = X(R) Z(R) mod n
    for (prime q ∈ [r + 2, r + 2D]) { // loop over primes
        δ = (qr) / 2 // distance to next prime
        g = g((X[R] − X(Sδ))(Z(R) + Z(Sδ)) − α + βδ) mod n
    }
    (R, T) = (addh(R, SD, 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, B1 is the first-stage bound and B2 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 B1 to B2 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 Xr ZδXδ Zr 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 B1 to B2 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: