EECM: ECM using Edwards curves
The EECM-MPFQ softwareEECM-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.
InstallationEECM-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 http://eecm.cr.yp.to/eecm-mpfq-20100305.tar.bz2 tar -xjf eecm-mpfq-20100305.tar.bz2 cd eecm-mpfq-20100305 sh install
UseHere 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 23If, 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 cyclesYou can run eecm with several integers as input:
( echo 2718281828459045235360287471 echo 141592653589793238462643383279502884197 ) | eecmIntegers 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.
VersionThis is version 2010.03.05 of the mpfq.html web page.