A new implementation of the elliptic curve method of integer factorization using Edwards and Hessian curves
Files in This Item:
|Robinson_ucd_5090N_10085.pdf||2.43 MB||Adobe PDF||Download|
|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:||Cryptography; Edwards; Elliptic Curve; Hessian; Integer Factorization; Number Theory||Language:||en||Status of Item:||Peer reviewed|
|Appears in Collections:||Mathematics and Statistics Theses|
Show full item record
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.