A new implementation of the elliptic curve method of integer factorization using Edwards and Hessian curves

Files in This Item:
 File SizeFormat
DownloadRobinson_ucd_5090N_10085.pdf2.43 MBAdobe PDF
Title: A new implementation of the elliptic curve method of integer factorization using Edwards and Hessian curves
Authors: Robinson, Oisin Matthew
Advisor: McGuire, Gary
Permanent link: http://hdl.handle.net/10197/8540
Date: 2015
Online since: 2017-11-15T02:00:10Z
Abstract: In this thesis, three main ideas characterise a new implementation of the Elliptic Curve Method (ECM) of integer factorization. The first idea is the use of Edwards/Hessian curves for all elliptic curve computations, including stage 2. The second idea is the use of families of elliptic curves with larger torsion subgroup over quartic number fields, in particular $\Z/4\Z\oplus\Z/8\Z$ for a family of Edwards curves, and $\Z/6\Z\oplus\Z/6\Z$ for a family of Hessian curves. The third idea is the generation of respectively hundreds/a few thousand of such curves from families given by Jeon/Kim/Lee, which have small parameters and a point of infinite order having small projective coordinates, leading to improved efficiency in scalar multiplication. The curves are generated using SAGE. The FFT continuation for stage 2 is implemented. The performance of the software is analysed and compared to the leading implementations, in terms of effectiveness/speed/memory usage. The implementation is tested on ICHEC's Fionn cluster. The use of Hessian curves in an implementation of ECM appears new. A new discovery is that EECM-MPFQ's `good curves' for ECM having torsion $\Z/2\Z\oplus\Z/8\Z$ are a subset of the Jeon-Kim-Lee $\Z/4\Z\oplus\Z/8\Z$ family, yielding many hundreds more good curves than the $100$ from two torsion families produced for EECM-MPFQ, not to mention several thousand curves from the $\Z/6\Z\oplus\Z/6\Z$ family with small parameters. This remediates one drawback of EECM-MPFQ - lack of good curves. Another discovery is that, for small-parameter Hessian curves, the speed of the addition formula is particularly fast, allowing Hessian scalar multiplication without windowing to compete with Edwards scalar multiplication with windowing. Since windowing is not required, the associated higher memory cost is not incurred. This has a beneficial consequence for ECM in memory-constrained environments such as when implemented on GPUs. This in turn may benefit the sieving stage of the number field sieve.
Type of material: Master Thesis
Publisher: University College Dublin. School of Mathematics and Statistics  
Qualification Name: M.Sc.
Copyright (published version): 2015 the author
Keywords: CryptographyEdwardsElliptic CurveHessianInteger FactorizationNumber Theory
Other versions: http://dissertations.umi.com/ucd:10085
Language: en
Status of Item: Peer reviewed
This item is made available under a Creative Commons License: https://creativecommons.org/licenses/by-nc-nd/3.0/ie/
Appears in Collections:Mathematics and Statistics Theses

Show full item record

Page view(s) 50

Last Week
Last month
checked on Dec 4, 2021


checked on Dec 4, 2021

Google ScholarTM


If you are a publisher or author and have copyright concerns for any item, please email research.repository@ucd.ie and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.