Breadcrumb

 
 

Lenstra's factoring method with elliptic curves

Title:

Lenstra's factoring method with elliptic curves

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

[img]
Preview
PDF - Accepted Version
1359Kb

Abstract

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.
Program:Mathematics and Statistics
Date:2005
Thesis Supervisor(s):David, Chantal
ID Code:8466
Deposited By:Concordia University Libraries
Deposited On:18 Aug 2011 14:26
Last Modified:18 Aug 2011 14:26
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

Document Downloads

More statistics for this item...

Concordia University - Footer