# Elliptic curve factoring

The details of the *elliptic curve factoring algorithm* are beyond the scope of this book; nevertheless, a rough outline follows. The success of Pollard's *p—* 1 algorithm hinges on *p -* 1 being smooth for some prime divisor *p* of n; if no such *p* exists, then the algorithm fails. Observe that *p -* 1 is the order of the group Z*. The elliptic curve factoring algorithm is a generalization of Pollard’s *p —* 1 algorithm in the sense that the group Z* is replaced by a random elliptic curve group over Z_{p}. The order of such a group is roughly uniformly distributed in the interval [p+1-2 *^/p. p+*1+2 *sfp ■* If the order of the group chosen is smooth with respect to some pre-selected bound, the elliptic curve algorithm will, with high probability, find a non-trivial factor of *n.* If the group order is not smooth, then the algorithm will likely fail, but can be repeated with a different choice of elliptic curve group.

The elliptic curve algorithm has an expected running tune of L_{p}[|, */2]* (see Example 2.61 for definition of *L _{p})* to find a factor

*p*of

*n.*Since this running time depends on the size of the prime factors of n, the algorithm tends to find small such factors first. The elliptic curve algorithm is, therefore, classified as a special-purpose factoring algorithm. It is currently the algorithm of choice for finding / -decimal digit prime factors, for

*t <*40, of very large composite integers.

In the hardest case, when *n* is a product of two primes of roughly the same size, the expected running time of the elliptic curve algorithm is *L _{n}[,* 1], which is the same as that of the quadratic sieve (§3.2.6). However, the elliptic curve algorithm is not as efficient as the quadratic sieve in practice for such integers.

# Random square factoring methods

The basic idea behind the random square family of methods is the following. Suppose *x *and *у* are integers such that *x*^{2}* = y** ^{2}* (mod n) but

*x ф ±y*(mod n). Then

*n*divides

*x*

^{2}*— y*

^{2}*= (x — y)(x+y)*but

*n*does not divide either

*(x—y)*or

*(x+y).*Hence, gcd(x—

*y, n)*must be a non-trivial factor of

*n.*This result is summarized next.

3.18 Fact Let *x, y,* and*n* be integers. If *x** ^{2}* =

*y*

*(mod ») but*

^{2}*x ф ±y*(mod n), thengcd(a;—

*y, n)*is a non-trivial factor of

*n.*

The random square methods attempt to find integers *x* and *у* at random so that *x*^{2}* = y** ^{2 }*(mod

*n).*Then, as shown in Fact 3.19, with probability at least A it is the case that

*x ф ±y*(mod n), whence gcd(;r -

*y. n)*will yield a non-trivial factor of n.

- 3.19 Fact Let
*n*be an odd composite integer that is divisible by*к*distinct odd primes. If*a*€ Z*, then the congruence*x*^{2}*= a*(mod n) has exactly^{2}*2*solutions modulo^{k}*n,*two of which are*x = a*and*x = -a.* - 3.20 Example Let
*n =*35. Then there are four solutions to the congruence*x*= 4 (mod 35),^{2}

namely *x =* 2,12, 23, and 33. □

A common strategy employed by the random square algorithms for finding *x* and *у* at random satisfying *x** ^{2}* =

*y*

*(mod*

^{2}*n)*is the following. A set consisting of the first

*t*primes

*S = {pi,P*

*2*

*, ■ ■ ■*,

*pt*} is chosen;

*S*is called the

*factor base.*Proceed to find pairs of integers

*(a, , bf)*satisfying

(i) *a*^{2}* = bi* (mod n); and

(ii) *bi =* П'_{=}1 *Pj ^{1}* >

*> 0; that is,*

^{e}ij*b*is /^-smooth.

_{t}Next find a subset of the 6;’s whose product is a perfect square. Knowing the factorizations of the *b,* ’s, this is possible by selecting a subset of the *h,* ’s such that the power of each prime *pj* appearing in their product is even. For this purpose, only the parity of the non-negative integer exponents ey needs to be considered. Thus, to simplify matters, for each *i,* associate the binary vector *v _{t}* = (ua, v,2,... ,

*v*

_{it}) with the integer exponent vector (e,i, e,2,....

*e*such that uy = ey mod 2. If

_{it})*t*+ 1 pairs (a*,

*bi)*are obtained, then the /-dimensional vectors

*v, V*

*2*

*, ■ ■*.,

*v*must be linearly dependent over Z2. That is, there must exist a non-empty subset

_{t+}i*T*C {1,2,... ,

*t*+ 1} such that X^:

_{€}t

*0*

^{v}*^{=}^{over}^2. and hence ILer *

^{s 3}perfect square. The set

*T*can be found using ordinary Unear algebra over Z2. Clearly, I

*is also a perfect square. Titus setting*

_{l(}__{T}of*x =*a, and

_{l(zT}*у*to be the integer square root of Ц

_{;еГ}

*b,*yields a pair of integers (

*x*,

*y)*satisfying

*x*(mod

^{2}= y^{2}*n).*If this pair also satisfies

*x ф ±y*(mod n), then gcd(ar -

*y. n)*yields a non-trivial factor of

*n.*Otherwise, some of the (a*,

*bi)*pairs may be replaced by some new such pahs, and the process is repeated. In practice, there will be several dependencies among the vectors

*vi,V*

*2*

*, ■ ■■ ,vt+i,*and with high probability at least one will yield an (

*x,y)*pah satisfying

*x ф ±y*(mod n); hence, this last step of generating new (ay 6,) pahs does not usually occur.

This description of the random square methods is incomplete for two reasons. Firstly, the optimal choice of f, the size of the factor base, is not specified; this is addressed in Note 3.24. Secondly, a method for efficiently generating the pahs (ay *bi )* is not specified. Several techniques have been proposed. In the simplest of these, called *Dixon’s algorithm, ai* is chosen at random, and *b, = a ^{2}* mod

*n*is computed. Next, trial division by elements in the factor base is used to test whether

*b,*is -smooth. If not, then another integer a, is chosen at random, and the procedure is repeated.

The more efficient techniques strategically select an *a,* such that 6,; is relatively smafi. Since the proportion of p_{(}-smooth integers in the interval *[2,x]* becomes larger as *x* decreases, the probability of such *b,* being /^-smooth is higher. The most efficient of such techniques is the quadratic sieve algorithm, which is described next.