He, Xun (2005) Lenstra's factoring method with elliptic curves. Masters thesis, Concordia University.
- Accepted Version
Suppose that we want to factorize an integer N. We can use Lenstra's method, which is based on elliptic curves over finite fields, to find the smallest non-trivial prime factor p of N. The success of Lenstra's algorithm depends on the probability to find an elliptic curve over the finite field with p elements such that the number of points on the curve doesn't have large prime factor. One advantage of Lenstra's algorithm is that we can try different curves to increase the success probability. Lenstra's algorithm has sub-exponential running time. In this thesis, we study Lenstra's algorithm and an implementation due to Brent, which has reduced the theoretical running time, under certain circumstances. We state their success conditions, success probabilities and running times, and discuss the relevant proofs. We also use PARI to implement this algorithm with Lenstra's and Brent's methods, do some tests, and collect some data which verify the theoretical results.
|Divisions:||Concordia University > Faculty of Arts and Science > Mathematics and Statistics|
|Item Type:||Thesis (Masters)|
|Pagination:||vi, 60 leaves ; 29 cm.|
|Degree Name:||M. Sc.|
|Program:||Mathematics and Statistics|
|Thesis Supervisor(s):||David, Chantal|
|Deposited By:||Concordia University Libraries|
|Deposited On:||18 Aug 2011 18:26|
|Last Modified:||18 Aug 2011 18:26|
Repository Staff Only: item control page