## 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:

S_{1}=doubleh(Q)

S_{2}=doubleh(S_{1})

for (d∈ [1,D]) { // this loop computesS= [2_{d}d]Q

if (d> 2)S=_{d}addh(S_{d−1},S_{1},S_{d−2})

β_{d}=X(S)_{d}Z(S) (mod_{d}n)

}

g= 1

B=B_{1}− 1 //Bis odd

T= [B− 2D]Q// via Algorithm 7.2.7

R=B[Q] // via Algorithm 7.2.7

for (r=B;r<B_{2};r=r+ 2D) {

α =X(R)Z(R) modn

for (primeq∈ [r+ 2,r+ 2D]) { // loop over primes

δ = (q−r) / 2 // distance to next prime

g=g((X[R] −X(S_{δ}))(Z(R) +Z(S_{δ})) − α + β_{δ}) modn

}

(R,T) = (addh(R,S_{D},T),R)

}

g=gcd(g,n)

if (1 <g<n) returng// found a nontrivial factor ofn

In the notation of Crandall and Pomerance, *B*_{1} is the first-stage bound and *B*_{2} 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 3*D* *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*_{1} to *B*_{2} are processed in segments of size 2*D*, 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*has a nontrivial gcd with

_{r}*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*_{1} to *B*_{2} 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.