Login | Register

Lenstra's factoring method with elliptic curves


Lenstra's factoring method with elliptic curves

He, Xun (2005) Lenstra's factoring method with elliptic curves. Masters thesis, Concordia University.

[thumbnail of MR10213.pdf]
Text (application/pdf)
MR10213.pdf - 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)
Authors:He, Xun
Pagination:vi, 60 leaves ; 29 cm.
Institution:Concordia University
Degree Name:M. Sc.
Thesis Supervisor(s):David, Chantal
Identification Number:LE 3 C66M38M 2005 H4
ID Code:8466
Deposited By: Concordia University Library
Deposited On:18 Aug 2011 18:26
Last Modified:13 Jul 2020 20:04
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top