From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Factorising numbers Date: 24 Feb 1995 05:56:18 GMT In article <793557609snz@wincoll.demon.co.uk>, Thomas O. Womack wrote: >I found references to the 'number field sieve', the 'multiple polynomial >quadratic sieve', and the 'elliptic curve' method of factorisation. I'd >quite like to implement these, just to see what happens; however, I couldn't >find any references to the number field sieve even in the neighbourhood >university library, and the references I found for the other two were >utterly incomprehensible. >Has anyone got the algorithms for these? More difficult, does anyone >know why they work? I am an A-level student with Maths and Further Maths, >have read Davenport on number theory and the like; are these algorithms >likely to be far above my head? If so, post them anyway - someone must >understand them!? I'm posting a guide to the Elliptic Curve method secure in the knowledge that some of the key players read this newsgroup from time to time and will be sure to correct any inaccuracies below :-) I'd have to say the method of factoring with elliptic curves is in spirit really quite similar to factoring with the Fermat theorem, with one important twist, which I will reveal at the end. -------------------------------- Let me discuss first the Fermat theorem method. Suppose n is the number to be factored. Pick any integer a strictly between 1 and n. If d=gcd(a,n) is not 1, you're in luck: you now have proper divisor d of n. (For our purposes we'll say we're done; of course, you might want to factor d and n/d .) (I should remark that the computation of the gcd is quite rapid by Euclid's algorithm and does not require factoring n .) Most likely, of course, you will find a is relatively prime to n. So now what? Well, let's pick a really large integer N (I'll show you a good N in a moment). It's really quite easy to compute a^N mod n; basically you express N in binary notation and repeatedly square a, storing and occasionally multiplying your answer. Then I ask you to compute gcd(a^N - 1, n). As before, we're done if this gcd is not 1 or n. (Actually if the gcd is n we can probably factor n by backtracking a little and finding a smaller N giving a proper divisor for this gcd. I won't discuss this in this post.) So then the real question is, Why should we expect a gcd other than 1? Well, suppose p is a prime factor of n. Then we have already ruled out the possibility that p | a, so by the Fermat theorem, a^(p-1) = 1 mod p. I must stress that this is really the Lagrange theorem: a is in the multiplicative group of Z/pZ which has order p-1. Anyway, it follows that if N is a multiple of (p-1) then a^N = 1 mod p, too, so that p divides gcd(a^N-1, n). So the trick is just to find an N which is a multiple of (p-1). This looks like cheating because you can't really find such an N unless you know what p is, which means you have to factor your original n. But it's not cheating, really. What you can always do is _hope_ that (p-1) is just a product of small primes, perhaps primes less than log(n). If that really is the case, write p-1 = Prod q^e_q (q = 2, 3, 5, ...). Of course since p < n we certainly have e_2 < log_2(n), e_3 G_p whenever p|n; above I used the group G_n = (Z_n)^*; this group will be different. I'll compute a large N , then pick an element a in the group G_n, then compute a^N in G_n. If the group G_p happens to have an order which is the product of small primes, then f(a^N) = f(a)^N will be the identity, so that a^N will lie in the kernel of f. Roughly speaking this kernel will (as with the Fermat method) consist of "multiples of p", so by computing a gcd of n and this "multiple of p", we'll have a divisor of n (larger than 1). So I have to tell you what this new group is. I also have to tell you why this method is better than the Fermat method it resembles; but first things first. (Note: I will write the group additively from now on.) OK, here's the group. Pick any integers A and B and let G_n be the set of solutions (x,y) in (Z_n)^2 to the equation y^2 = x^3+Ax+B. (Actually G_n is supposed to be this set together with another element I'll just call O; it's not a point in (Z_n)^2, but it can be viewed as a "point at infinity" in the projective space P^2(Z_n).) In order for me to make this into a group I have to define a binary operation on G_n. This is essentially the familiar chord-and-tangent process for generating solutions to cubics which has recently been mentioned in this group. One can view the binary operation in either of two ways: 1) Given two points in G_n add them as follows: draw the line joining them, and find the other point P where this line meets the curve y^2=x^3+Ax+B. Then draw the vertical line through P and find the other point P' where this new line meets the curve. This P' is the sum of the first two points. (If the original two points are equal, use the tangent line there to play the role of the first line above). 2) Given points (x,y) and (x',y') their sum is (x'', y'') where x''=-(x+x')+m^2, y''=-[y+m(x''-x)]. Here, m=(y'-y)/(x'-x) if x and x' are distinct, and m=(3x^2+A)/(2y) if x=x' and y' is not -y. Either definition is a bit incomplete. I need to tell you first that O+P=P+O=P for any P. Furthermore, the sum of (x,y) and (x, -y) is not covered either by (1) or (2); in this case we define their sum to be O. (There's more to worry about, too. One needs to know that there are no singular points, which means you have to rule out some special (A,B)'s. Also, if n is not prime, it may not be possible to divide by (x'-x), and there may be pairs of points (x,y) with the same x but with y coordinates which are neither equal nor negative. All these "problems" will actually work in our favor for factoring). What's not clear from either definition is that this should be an _associative_ binary operation, but it is! Then it's clear that G_n is an Abelian group. (Again, I'll be honest: it's really only a group when n is prime.) Observe that for each x there can be at most 2 points (x,y) in G_p, so |G_p| <= 2p. As it turns out, a bit more is true: |G_p - (p+1)| < 2sqrt(p), so the order is really quite close to p. But certainly we can use Lagrange's Theorem again and say that for any point a in G_p we have N.a = O where N = Prod q^log_q(n), as long as we take this product to be over all primes dividing the order of G_p. As with the Fermat method, we typically take N to be the product over all primes up to, say, log(n), just hoping that the order of G_p will be a product of small primes. Again copying the Fermat method, we take an a in G_n, compute this multiple N.a in G_n, knowing that if the resulting coordinates were reduced mod p, we'd have the identity element of the group G_p. Since the identity element is just that added point O, it's a little better to view the previous sentence this way: We compute repeated sums in G_n in an attempt to compute N.a, knowing that at some stage we will be adding two points in G_n whose images in G_p are negatives of each other, so that mod p they are of the form (x,y) and (x,-y). Therefore, the sum of their second coordinates is zero mod p, and so has a nontrivial gcd with n. ---> So here's the method: <--- (1) Fix N as above (2) Pick an elliptic curve (i.e. pick A and B) and a point a on it. (P.S. - It's easier to pick the point and then find a curve that includes it!) (3) Compute the multiple N.a in G_n as a sequence of repeated additions. Before each addition, calculate gcd(n, y+y') where y and y' are the second-coordinates of the two points; stop if this gcd > 1. Note that computing the sum in the group requires computing m = (y'-y)/(x'-x), and thus requires inverting x'-x. There is only a problem with this if x'-x has a nontrivial gcd with n, which from our perspective is not a "problem" at all but a blessing! (In case x'=x mod n, then because (x,y) and (x',y') both satisfy the cubic, we get (y'-y)(y'+y)=0 mod n, so that either one of these factors has a nontrivial gcd with n (yay!), or else y'= +- y mod n; if y'=y, we are doubling a point in G_n and have a formula for that; if y'=-y, the points sum to O.) This method will work as long as |G_p| is only divisible by the primes dividing N. (Well, there are some special cases to worry about, akin to what I had in mind the last time I used the word "probably".) -------------------------------- No doubt the reader is wondering what all the hullabaloo is, given that this method is so complicated compared to the Fermat method, and yet seems to give the same kind of answer. The difference is this: in the Fermat method, we have only one group to use (namely Z/p^*), and if its order (p-1) had large factors, we were stuck. In the elliptic curve method, we are stuck if |G_p| has large factors BUT there is more than one group available. Indeed by choosing new A and B we get a new group G_p AND the order of this group will likely be different! Roughly speaking, one can get |G_p| to be just about any number in the interval (p+1-sqrt(p), p+1 + sqrt(p)), so that our success in finding the prime factor p depends only on how likely it is that a number in this interval has only small prime factors. Judging this precisely requires a knowledge of prime distributions comparable to the Generalized Riemann Hypothesis, so for the most part we content ourselves with heuristic estimates of success rates. Frankly, I think it's more fair to say, "the proof is in the pudding"! There are a number of technical devices used to speed up the process considerably. For example, it is common to introduce a 2-stage process, one to account for all possible small prime divisors of |G_p|, as above, and the other to handle the case that the rest of |G_p| is prime. Also, a significant amount of computation time is spent adding elements in the elliptic curve, so it is worthwhile to find other, more suitable canonical forms for an elliptic curve, to code that routine in low-level machine language, and so on. Finally, I ought to mention that trial division by small primes is a lot faster than the E.C. method, so it's worth while trying, say, the first thousand or so primes individually. As you may have noticed, the crucial theoretical determinant of factoring speed is the size of the prime divisors of n (rather than the size of n itself). Today's workstations can find 20- or 30-digit prime factors rather rapidly. Even a PC can deliver 10+ digit primes while you wait. So for your run-of-the-mill 100-digit number, the elliptic curve method has shown itself to be a useful workhorse. On the other hand, it only quickly finds the _small_ prime factors, not _all_ the factors. Moreover, the extra time needed for a few extra digits is quite significant. When such other considerations must be taken into account, other methods of factoring are typically superior. It shouldn't surprise you to hear: this is an active field of research. dave