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

Files in This Item:
File Description SizeFormat 
Robinson_ucd_5090N_10085.pdf2.43 MBAdobe PDFDownload
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
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
Language: en
Status of Item: Peer reviewed
Appears in Collections:Mathematics and Statistics Theses

Show full item record

Google ScholarTM

Check


This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.