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

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.