EECM: ECM using Edwards curves 

The EECMMPFQ softwareEECMMPFQ is a fast implementation of the ellipticcurve method of factoring integers. EECMMPFQ was introduced in the paper "ECM using Edwards curves" by Bernstein, Birkner, Lange, and Peters. EECMMPFQ uses fewer modular multiplications than the wellknown GMPECM software, takes less time than GMPECM, and finds more primes than GMPECM.EECMMPFQ now also supports additional curve choices described in the paper "Starfish on strike" by Bernstein, Birkner, and Lange. InstallationEECMMPFQ requires an amd64 (x8664) 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, GMPECM (which is not yet compatible with GMP 5 because GMP 5 changed __GMP_BITS_PER_MP_LIMB to GMP_LIMB_BITS), NTL, MPFQ, and EECMMPFQ in subdirectories of your home directory:export PREFIX=$HOME cd $PREFIX wget ftp://ftp.gnu.org/gnu/gmp/gmp4.3.2.tar.bz2 tar xjf gmp4.3.2.tar.bz2 cd gmp4.3.2 ./configure prefix=$PREFIX enablecxx make make check make install cd $PREFIX wget http://gforge.inria.fr/frs/download.php/22124/ecm6.2.3.tar.gz tar xzf ecm6.2.3.tar.gz cd ecm6.2.3 ./configure prefix=$PREFIX withgmp=$PREFIX make make check make ecmparams make make check make install cd $PREFIX wget http://www.shoup.net/ntl/ntl5.5.2.tar.gz tar xzf ntl5.5.2.tar.gz cd ntl5.5.2/src ./configure DEF_PREFIX=$PREFIX NTL_GMP_LIP=on make make check make install cd $PREFIX wget http://mpfq.gforge.inria.fr/mpfq1.0rc2.tar.gz tar xzf mpfq1.0rc2.tar.gz mkdir mpfq cd mpfq cmake $PREFIX/mpfq1.0rc2/src \ DCMAKE_INSTALL_PREFIX=$PREFIX \ DGMP_INCLUDE_PATH=$PREFIX/include \ DGMP_LIB=$PREFIX/lib/libgmp.a \ DGMP_LONGLONG_PATH=$PREFIX/gmp4.3.2 \ DGMP_IMPL_PATH=$PREFIX/gmp4.3.2 make make check make install cd $PREFIX wget http://eecm.cr.yp.to/eecmmpfq20100305.tar.bz2 tar xjf eecmmpfq20100305.tar.bz2 cd eecmmpfq20100305 sh install UseHere is an example of factoring an integer with EECMMPFQ:echo 314159265358979323  eecm The output of eecm has three sections. The first section shows parameters that you can adjust: command = eecm16 10 1024 270 3 1 1 version = 20100305 words = 1 torsion = 6 numcurves = 10 B1 = 1024 (stage1 bound) d1 = 270 (stage2 giantstep size) e = 3 (stage2 Dickson degree) ijratio = 1 (stage2 giant steps per baby step) prodstrategy = 1 (stage2 product strategy) first curve = 3 4 32 23If, for example, you want to apply 100 curves to a 1word integer with B1 = 300, you can run eecm16 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 EECMMPFQ 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. 