Abstract
Li, Zhihong. Ph.D., Purdue University, December, 2006. Elliptic Curve Factoring
Method via FFTs with Division Polynomials. Major Professor: Samuel S. Wagstaff,
Jr..
In 1985, H. W. Lenstra, Jr. discovered a new factoring method, the Elliptic Curve
Method (ECM), which efficiently finds 20- to 30- digit prime factors. On January
15, 2001, C. P. Schnorr proposed an idea to apply division polynomials for ECM. In
this thesis, we modify and implement the idea in detail, analyze the complexity of
the algorithm and the probability of success.
We first extend the concept of division polynomial to a univariate case with the
parameter a in the Weierstrass form y2 = x3 +ax+b as the variable. We generalize
a result about the degree of this implied univariate division polynomial. Then we
discover an algorithm to efficiently generate the m-th univariate division polynomial
and determine the complexity of the algorithm.
We then present the main algorithm of this thesis, which is the main result of the
thesis as well. We demonstrate in both algebraic and geometric ways the sufficient
conditions for the algorithm to be successful. We analyze the probability of success
and prove the related results. To demonstrate the structure of the main algorithm,
we divide it to several parts and introduce every part in detail. Then we propose
and prove a theorem about the complexity of the main algorithm.
We also present an optimization of the main algorithm for a family of numbers
with specific form. This family is of great interest as well. We show that for this
family, the optimal algorithm can factor numbers even faster and also remove the
memory restriction of the multiple m of the point on the elliptic curves, which is
also the index of the implied division polynomial being used.
vii
At the end, we address some issues related to the implementation of the algorithm.
With the algorithm, we can find some 40-digit primes on a 1.86GHz 1066FBS
PC with 4GB DDR2 SDRAM at 533MHz. It also finds some 50-digit primes. Now
we are trying the algorithm on 60-digit primes and we hope that the algorithm will
find some 70-digit primes.
