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 Zp. 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 Lp[|, /2] (see Example 2.61 for definition of Lp) 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 Ln[, 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 x2 = y2 (mod n) but x ф ±y (mod n). Then n divides x2 — y2 = (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, andn be integers. If x2 = y2 (mod ») but 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 x2 = y2 (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 x2 = a2 (mod n) has exactly 2k solutions modulo n, two of which are x = a and x = -a.
  • 3.20 Example Let n = 35. Then there are four solutions to the congruence x2 = 4 (mod 35),

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

A common strategy employed by the random square algorithms for finding x and у at random satisfying x2 = y2 (mod n) is the following. A set consisting of the first t primes S = {pi,P2, ■ ■ ■ , pt} is chosen; S is called the factor base. Proceed to find pairs of integers (a, , bf) satisfying

(i) a2 = bi (mod n); and

(ii) bi = П'=1 Pj1 > eij > 0; that is, bt is /^-smooth.

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 vt = (ua, v,2,... , vit) with the integer exponent vector (e,i, e,2,.... eit) such that uy = ey mod 2. If t + 1 pairs (a*, bi) are obtained, then the /-dimensional vectors v, V2, ■ ■ ., vt+i must be linearly dependent over Z2. That is, there must exist a non-empty subset T C {1,2,... , t + 1} such that X^:t v* = 0 over ^2. and hence ILer *s 3 perfect square. The set T can be found using ordinary Unear algebra over Z2. Clearly, I l(_T of is also a perfect square. Titus setting x = l(zT a, and у to be the integer square root of Ц;еГ b, yields a pair of integers (x, y) satisfying x2 = y2 (mod 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,V2, ■ ■■ ,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, = a2 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.

< Prev   CONTENTS   Source   Next >