From msuinfo!uwm.edu!vixen.cso.uiuc.edu!howland.reston.ans.net!noc.near.net!uunet!utcsri!newsflash.concordia.ca!sifon!homer.cs.mcgill.ca!not-for-mail Fri Jul 30 12:47:55 1993 Path: msuinfo!uwm.edu!vixen.cso.uiuc.edu!howland.reston.ans.net!noc.near.net!uunet!utcsri!newsflash.concordia.ca!sifon!homer.cs.mcgill.ca!not-for-mail From: jerry@binkley.cs.mcgill.ca (Jerry Kuch) Newsgroups: sci.crypt,sci.math,sci.math.symbolic Subject: Re: Looking for an article (factoring large numbers) Date: 28 Jul 1993 18:00:24 -0400 Organization: SOCS - McGill University, Montreal, Canada Lines: 87 Message-ID: <236sto\$amq@binkley.cs.mcgill.ca> References: NNTP-Posting-Host: binkley.cs.mcgill.ca Xref: msuinfo sci.crypt:18216 sci.math:48477 sci.math.symbolic:8362 In article freitag@elrond.toppoint.de (Claus Schoenleber) writes: >Someone told me about a method for factoring large numbers >using elliptic equations. I didn't find anything about that. >Could someone give me a pointer? I think you're talking about Lenstra's work. You can find it in: Lenstra, H.W. Jr. "Factoring Integers with elliptic curves." Annals of Mathematics, 126 (1987) 649-673. Essentially the same text exists in a University of Amsterdam tech report and also, I believe, in one from MSRI. Lenstra's algorithm is based on the Pollard p-1 method for integer factorization. In this scheme, given an integer, n, to be factored, you: 1. Choose an integer k such that k is a multiple of all (or most of the) integers less than some bound B where B can be as simple as lcm(all ints <= B) or B!. 2. Choose an integer, a from the set {2, n-2} 3. Compute a^k mod n efficiently (there are easy tricks for this that are better than multiplying a by itself k times) 4. Compute d = gcd(a^k - 1, n) using the Euclidean algorithm and the result from step 3. 5. If d isn't a nontrivial divisor of n then choose new values for a and/or k. Then start over. If p is an unknown prime factor of n, and p-1 has no large prime divisors then the above method is quite likely to find the factor, p. To get some idea of how it works, assume that k is divisible by all of the positive integers less than or equal to the bound B, above. Suppose as well that p is a prime divisor of n such that p-1 is the product of small prime powers all less than B. If so, then k must be a multiple of p-1 since it is a multiple of all the prime powers whose product is p-1. By Fermat's Little Theorem a^k is congruent to 1 modulo p. Because of this p divides gcd(a^k-1,n) and we only fail to produce nontrivial factors of n (in step 4 of the above algo) if a^k happens to be congruent to 1 mod n. Lenstra's method remedies the following defect. The above method suffers when all of n's prime divsiors, p are such that p-1 is divisible by a relatively large prime, or, by a relatively large prime power. The problem in essence is that we're relying on the group (Z/pZ)^* as p runs through all of n's prime divisors. For a given n, these groups aare all fixed, and if all of these groups have order divisible by a large prime they're next to useless. The elliptic curve method overcomes the problem by using elliptic curves over F_p = Z/pZ. These curves provide an easy source of different groups to choose from while performing the factorization, enough in fact that in practice we can typically expect to find one whose order is not divisible by a large prime or prime power. If we end up choosing a group over F_p that suffers from the problem described above, we toss it out by randomly choosing the group corresponding to another elliptic curve over F_p. Maple's integer factorization package provides the option of using Lenstra's elliptic curve method (as does Mathematica). It is interesting to note that it seems to used a pre-fixed sequence of elliptic curves and thus, the performance of the package on factoring a sequence of integers may vary extremely widely depending on what order they are input in. I don't know of a good way to intelligently feed Maple to avoid this situation; even knowing in advance what sequence Maple tries, it's still probably a big grind to test the suitability of a given group for a given problem (since it amounts to trying to solve the problem anyway). If you're really interested in integer factorization you might also want to look into a couple of other algorithms: - multiple polynomial quadratic sieve - the number field sieve The asymptotic performance of Lenstra's algo is of the same order as the conjectured time estimates for some of today's best factoring algorithms. It does have a couple of advantages though. One of concern to implementors is the fact that is has a pretty small storage requirement. Also, it is exceptionally fast when n is divisible by a prime much less than n^(1/2). Also if the factors of n are relatively small, it tends to beat its competitors whose runtimes tend to be moreorless independent of the size of individual factors. -- Jerry Kuch jerry@cs.mcgill.ca