In this lecture we will show how elliptic curves over finite fields may be used to factor large composite numbers. More specifically, we illustrate a simplified version of Lenstra’s algorithm, which exploits the group structure on an elliptic curve to produce a factor of a given number. It is important to keep in mind that this is a probabilistic algorithm in that it is not guaranteed to produce a nontrivial factor of a given composite number in any finite amount of time. However, “in general” one can expect the algorithm to produce a nontrivial factor given the “right” circumstances, and it is significant in its own right that elliptic curves have this application.

1 Computational complexity considerations

The (efficient) factoring of large numbers is a problem of central interest today. Many encryption schemes (most notably RSA) rely on the tested maxim that factoring takes a lot of time. Indeed, the most “obvious” factoring method–trial division– is pretty bad because one has to perform about \sqrt{n}/ log \sqrt{n} divisions (roughly the number of primes less than \sqrt{n}). What we would really like is a factoring algorithm that works in something like log n operations, but this may be too much to hope for. When considering problems of computational complexity, algorithms are usually divided into two classes. There are those algorithms (like trial division, above) that take about n^{a} operations (for some fixed positive a), and there are those algorithms that can be executed in C log n operations for some fixed constant C. The former algorithms are said to take exponential time, while the latter take polynomial time. In general, polynomial time algorithms are considered efficient, while exponential time algorithms are considered inefficient.

Since we will be investigating computational algorithms that make heavy use of Euclid’s algorithm and arithmetic modulo n it is good to know that these computations are quite efficient. Indeed, it is not difficult to determine [1][pg. 15] that in practice, the GCD of two integers b, c can be computed in about 3 log c iterations of Euclid’s algorithm. Since each iteration of the algorithm requires only division and subtraction, we see that Euclid’s algorithm works in polynomial time. We shall also need to compute powers a^{d} of some integer a modulo n. In order to implement this efficiently, we compute a^{d} by repeated squaring, working modulo n. For example, if we want to compute 3^{20} mod 50 we compute

3^{2} ≡ 9 mod 50
3^{4} ≡ 9^{2} ≡ 31 mod 50
3^{8} ≡ 31^{2} ≡ 11 mod 50
3^{16} ≡ 11^{2} ≡ 21 mod 50
3^{20} ≡ 3^{16} · 3^{4} ≡ 21 · 31 ≡ 1 mod 50.

Since we are really working with the binary expansion of d, the number of steps to compute a^{d} mod n is roughly the number of binary digits of d, or about log d, so this is a polynomial time algorithm.

2 Pollard’s p − 1 method

In order to motivate Lenstra’s algorithm for factoring using elliptic curves, we take a close look at another, simpler factoring algorithm.

Let n be some integer with a prime factor p. The basis of Pollard’s algorithm is the assumption that it is “likely” that the prime factors of p − 1 are small in comparison to p. One fixes a bound, B, as a guess for the size of the largest possible prime factor of p − 1, and forms the product

k = ∏_{q≤B} q^{⌊log_{q} B⌋},

which is taken over all primes q ≤ N. The idea is that k is very divisible by all the small primes that we expect to divide p − 1, and hence we expect p − 1 to divide k. Fermat’s theorem then tells us that we have

p|a^{k} − 1

for any nonzero a mod p and hence that p|d where

d = gcd(a^{k} − 1, n),

so that we have a nontrivial factor d of n. Since our goal is to compute gcd(a^{k} − 1, n), we only care about the value of a^{k} − 1 modulo n, and we have seen that this is a “cheap” operation in terms of computational time. Similarly, computing the GCD by Euclid’s algorithm is also inexpensive.

Example 1. Using Pollard’s method, factor n = 6380651.

We try a = 2, B = 9 so that

k = 2^{3} · 3^{2} · 5 · 7 = 2520 = 2^{12} + 2^{8} + 2^{7} + 2^{6} + 2^{4} + 2^{3}.

We readily compute (by repeated squaring, working modulo 6380651)

2^{1} = 2  2^{2} = 4  2^{4} = 16  2^{8} = 256
2^{16} = 65536  2^{32} = 789173  2^{64} = 4202423  2^{128} = 5994431
2^{256} = 5409973  2^{512} = 4188467  2^{1024} = 440743  2^{2048} = 1853005,

so that

2^{k} ≡ 256 · 65536 · 420243 · 5994431 · 5409973 · 1853005 ≡ 6347879 mod 6380651.

We now use Euclid’s algorithm to determine the GCD of n = 6380651 and 2^{k} − 1 = 6347879. We have

6380651 = 6347878 + 32773
6347879 = 193 · 32773 + 22689
32773 = 22689 + 10084
22689 = 2 · 10084 + 2521
10084 = 4 · 2521 + 0,

so that 2521|6380651. This leads to the factorization

6380651 = 2521 · 2531.

In many instances, pollard’s method is quite efficient. In some cases, though, notably when all the p factors of n have p − 1 divisible by large primes, it can become very slow, as the next example illustrates.

Example 2. Let n = 491389. It so happens that n = 383 · 1283 and 382 = 2 · 191 while 1282 = 2 · 641. Since both 191 and 641 are primes, we would have to take B = 191 before obtaining a nontrivial factor of n by Pollard’s method. Needless to say, this would involve a lot of computation.

The key feature of Pollard’s method is that it relies on the structure of the multiplicative groups

(ℤ/(p))^{×}

for factors p of the number n that we want to factor. This is a major limiting factor in the flexibility and efficiency of the algorithm since once n is specified, the groups ℤ/(p) that the algorithm exploits are fixed, and if it so happens that all prime factors p of n have p − 1 divisible by some large prime, then the computations involved are impractical and we are stuck. Lenstra’s algorithm sidesteps this difficulty by using the group of points on an elliptic curve to factor n, and as we shall see, there are many different groups for a given n corresponding to different elliptic curves.

3 Lenstra’s Algorithm

Suppose that we want to factor the composite integer n. Let E := E(q, r) be an elliptic curve over 𝔽_{p} given by the equation

y^{2} = x^{3} + qx + r,

and let P = (x, y) be any point on E(q, r). Since the number of points N_{p} := N_{p}(q, r) of E(q, r) over 𝔽_{p} is finite, any point of E has order dividing N_{p}. In particular, if N_{p}|k then we have kP = O. As with Pollard’s method, we make a guess as to the primes that can divide N_{p}(q, r) and form an appropriate k that is highly divisible by these primes. We are hoping that we will have N_{p}(q, r)|k. We then work modulo n and attempt to compute kP (in a manner that we shall describe). Either everything goes smoothly or we are unable to continue the process because for some m|k we have mP = O and when we try to compute mP, we are trying to find the coordinates for the point at infinity, which we think of as having infinite y coordinate. If this latter case happens, then we will be trying to “divide by 0” modulo n, or equivalently, we will be trying to invert some d with (d, n) ≠ 1. We have then found a nontrivial factor of n. Otherwise, we change the elliptic curve and initial point and repeat the process. We summarize this formally in the following algorithm.

Algorithm 1 (Lenstra). Let n be a composite number that we want to factor.

1. Pick some B > 0 and let π be the largest prime less than \sqrt{n} so that any prime factor of n is at most π.

2. Set M = ⌊π + 1 + 2\sqrt{π}⌋. this may seem somewhat arbitrary, but in fact, M is an upper bound for the number of points on E(q, r) over 𝔽_{p} for any p|n. This is essentially a famous theorem of Hasse.

3. Set

k = ∏_{q≤B} q^{⌊log_{q} M⌋},

where the product is taken over all primes at most B. We are picking k so that it will be likely that N_{p}|k for some p|n. The larger we take B, the more likely this is, on the other hand, the larger we take B, the more computations we will have to do.

4. Pick an elliptic curve E(q, r) together with a point P = (x, y) of E(q, r) (say over ℚ). We must first check that E is nonsingular over 𝔽_{p} for every prime p|n. This amounts to the condition (n, 4q^{3}+27r^{2}) = 1. If this fails, we either have a nontrivial factor of n, in which case we are done, or n|4q^{3} + 27r^{2}, in which case we pick a different elliptic curve.

5. Attempt to compute the coordinates of kP modulo n. Any time a division is necessary–for example in computing the inverse of y modulo n in the formula

(\frac{3x^{2} + q}{2y} ) − 2x,

we use the Euclidean algorithm. One computes kP by writing

k = l_{1}l_{2} ⋯ l_{s},

where l_{i} are primes and l_{1} ≤ l_{2} ≤ ⋯ ≤ l_{s}, and then computing l_{1}P, l_{2}(l_{1}P), …, kP using the method of repeated squaring and the binary expansion of each l_{i}, just as in Pollard’s method.

6. Either we are able to compute kP modulo n or at some point in the process we cannot divide modulo n because for some t ≤ s and some p|n we have N_{p}|l_{1}l_{2} ⋯ l_{t}, so that if L_{t} = l_{1}l_{2} ⋯ l_{t} then L_{t}P = O modulo p and we are trying to compute the inverse of some a modulo n with (a, n) > 1. The Euclidean algorithm then gives us a nontrivial factor of n, as desired. If we are in the former case, or if it so happens that a = n then we pick a different elliptic curve and begin again. Alternately, it may be necessary to choose a larger value of B.

The ability to just pick another elliptic curve and begin again is what makes Lenstra’s method so much more flexible than pollard’s algorithm. We now look at some examples of Lenstra’s algorithm.

Example 3. Using Lenstra’s algorithm, find a nontrivial factor of 1449533.

We use the family of elliptic curves E(a, −a), which all have the point P = (1, 1) on them. Since n = 1449533, we have π = 1201 so that M = 1271. We begin by trying B = 3, a = 1. Then we have k = 2^{10} · 3^{6}. Working modulo n we compute

2P, 4P, …, 2^{10}P, 3(2^{10}P), … kP

using the Euclidean algorithm whenever we must calculate inverses modulo n. We find

P = (1, 1)  2P = (2, 1449530)
2^{2}P = (765032, 208035)  2^{3}P = (35660, 378226)
2^{4}P = (1290470, 840473)  2^{5}P = (663017, 645623)
2^{6}P = (1051890, 1120876)  2^{7}P = (268555, 1155381)
2^{8}P = (774755, 989803)  2^{9}P = (851862, 449326)
2^{10}P = (382293, 1119221)  2^{10}3P = (326716, 22564)
2^{10}3^{2}P = (938879, 748249)  2^{10}3^{3}P = (1013556, 385270)
2^{10}3^{4}P = (179101, 1077013)  2^{10}3^{5}P = (432909, 801568)

However, when we try to compute kP we run into problems. Let Q = 2^{10}3^{5}P = (432909, 801568). Then we have

2Q = (1093968, 1064687)

and therefore when we try to compute

2Q + Q = (1093968, 1064687) + (432909, 801568)

we must compute the inverse of

1093968 − 432909 = 661059 mod 1449533.

Using Euclid’s algorithm we have

1449533 = 2 · 661059 + 127415
661059 = 5 · 127415 + 23984
127415 = 5 · 23984 + 7495
23984 = 3 · 7495 + 1499
7495 = 5 · 1499 + 0,

so that 1499|1449533. This leads to the factorization

1449533 = 967 · 1499.

References

[1] Niven, I., Zuckerman, H., and Hugh Montgomery. “An Introduction to the Theory of Numbers.” John Wiley & Sons, Inc. New York, 1991.