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: <CAvK7z.9x@elrond.toppoint.de>
NNTP-Posting-Host: binkley.cs.mcgill.ca
Xref: msuinfo sci.crypt:18216 sci.math:48477 sci.math.symbolic:8362
In article <CAvK7z.9x@elrond.toppoint.de> 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