EECM: ECM using Edwards curves
Introduction
EECM-MPFQ
Performance
Good curves

The EECM-MPFQ software

EECM-MPFQ is a fast implementation of the elliptic-curve method of factoring integers. EECM-MPFQ was introduced in the paper "ECM using Edwards curves" by Bernstein, Birkner, Lange, and Peters. EECM-MPFQ uses fewer modular multiplications than the well-known GMP-ECM software, takes less time than GMP-ECM, and finds more primes than GMP-ECM.

EECM-MPFQ now also supports additional curve choices described in the paper "Starfish on strike" by Bernstein, Birkner, and Lange.

Installation

EECM-MPFQ requires an amd64 (x86-64) UNIX/BSD/Linux/etc. system with gcc, g++, cmake, and m4. Here is how to install the current versions (as of 2010.03) of GMP 4, GMP-ECM (which is not yet compatible with GMP 5 because GMP 5 changed __GMP_BITS_PER_MP_LIMB to GMP_LIMB_BITS), NTL, MPFQ, and EECM-MPFQ in subdirectories of your home directory: 
     export PREFIX=$HOME

     cd $PREFIX
     wget ftp://ftp.gnu.org/gnu/gmp/gmp-4.3.2.tar.bz2
     tar -xjf gmp-4.3.2.tar.bz2 
     cd gmp-4.3.2
     ./configure --prefix=$PREFIX --enable-cxx
     make
     make check
     make install
   
     cd $PREFIX
     wget http://gforge.inria.fr/frs/download.php/22124/ecm-6.2.3.tar.gz
     tar -xzf ecm-6.2.3.tar.gz
     cd ecm-6.2.3
     ./configure --prefix=$PREFIX --with-gmp=$PREFIX
     make
     make check
     make ecm-params
     make
     make check
     make install
   
     cd $PREFIX
     wget http://www.shoup.net/ntl/ntl-5.5.2.tar.gz
     tar -xzf ntl-5.5.2.tar.gz
     cd ntl-5.5.2/src
     ./configure DEF_PREFIX=$PREFIX NTL_GMP_LIP=on
     make
     make check
     make install

     cd $PREFIX
     wget http://mpfq.gforge.inria.fr/mpfq-1.0-rc2.tar.gz
     tar -xzf mpfq-1.0-rc2.tar.gz
     mkdir mpfq
     cd mpfq
     cmake $PREFIX/mpfq-1.0-rc2/src \
     -DCMAKE_INSTALL_PREFIX=$PREFIX \
     -DGMP_INCLUDE_PATH=$PREFIX/include \
     -DGMP_LIB=$PREFIX/lib/libgmp.a \
     -DGMP_LONGLONG_PATH=$PREFIX/gmp-4.3.2 \
     -DGMP_IMPL_PATH=$PREFIX/gmp-4.3.2
     make
     make check
     make install
   
     cd $PREFIX
     wget https://eecm.cr.yp.to/eecm-mpfq-20100305.tar.bz2
     tar -xjf eecm-mpfq-20100305.tar.bz2
     cd eecm-mpfq-20100305
     sh install

Use

Here is an example of factoring an integer with EECM-MPFQ: 
     echo 314159265358979323 | eecm

The output of eecm has three sections. The first section shows parameters that you can adjust: 

     command = eecm1-6 10 1024 270 3 1 1
     version = 20100305
     words = 1
     torsion = 6
     numcurves = 10
     B1 = 1024 (stage-1 bound)
     d1 = 270 (stage-2 giant-step size)
     e = 3 (stage-2 Dickson degree)
     ijratio = 1 (stage-2 giant steps per baby step)
     prodstrategy = 1 (stage-2 product strategy)
     first curve = 3 4 32 23
If, for example, you want to apply 100 curves to a 1-word integer with B1 = 300, you can run eecm1-6 100 300 instead of simply eecm. You can specify -1 for the number of curves; then eecm will continue running until it finds a divisor. (Extra statistics option: You can specify -100 for the number of curves; then eecm will continue running through exactly 100 curves, whether or not it finds a divisor.)

The second section of output shows various precomputations that depend on the parameters but that do not depend on the integer being factored: 

     s bits = 1479
     trying m = 7 cost 13066
     trying m = 15 cost 12638
     trying m = 31 cost 12377
     trying m = 63 cost 12246
     trying m = 127 cost 12365
     trying m = 255 cost 12797
     trying m = 31 cost 12377
     trying m = 127 cost 12365
     trying m = 95 cost 12300
     trying m = 47 cost 12260
     trying m = 79 cost 12291
     trying m = 55 cost 12260
     trying m = 71 cost 12273
     trying m = 59 cost 12246
     trying m = 67 cost 12264
     trying m = 61 cost 12255
     trying m = 65 cost 12255
     trying m = 62 cost 12264
     trying m = 64 cost 12255
     m = 63 cost 12246
     cost: 0 curve, 0 ecdbl, 0 ecadd, 0 M, 0 S, 0 +, 0 I, 1457826 cycles
     stage 2: 334 ecops for 72 points
     B2 = 10744
     numj = 36
     numi = 36
     cost: 0 curve, 0 ecdbl, 0 ecadd, 0 M, 0 S, 0 +, 0 I, 423419 cycles

The third section of output is specific to the integer being factored: 

     n = 314159265358979323
     cost: 0 curve, 0 ecdbl, 0 ecadd, 0 M, 0 S, 0 +, 0 I, 55819 cycles
     trying (x1,y1) = (3/4,32/23)
     divisor 317213509 in stage 1
     cost: 1 curve, 1473 ecdbl, 215 ecadd, 6144 M, 5892 S, 10988 +, 0 I, 525458 cycles
You can run eecm with several integers as input: 
     (
       echo 2718281828459045235360287471
       echo 141592653589793238462643383279502884197
     ) | eecm
Integers with the same number of words will share precomputations. The current behavior of EECM-MPFQ is that integers with different numbers of words run in parallel without sharing precomputations.

Version

This is version 2017.01.22 of the mpfq.html web page.