Date:         Mon, 12 Sep 2005 11:44:25 -0400
Reply-To:     Bruce Dodson <bad0@LEHIGH.EDU>
Sender:       Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU>
From:         Bruce Dodson <bad0@LEHIGH.EDU>
Subject:      ECM record prime factor (66-digits) passes Quadratic Sieve
              benchmark (RSA129 = 64-digits times 65-digits)

ECM record prime factor (66-digits) passes Quadratic Sieve benchmark
(RSA129 = 64-digits times 65-digits)

I'm writing to report a remarkable new record prime factor for
the Elliptic Curve Method (ECM).  A 57-digit ECM record prime factor 
was the topic of a previous NMBRTHRY report [D].  An intermediate 
59-digit record was recently posted in [Z], with the release of an
update of software used in the ECMNET distributed computing project 
(<//www.loria.fr/~zimmerma/records/ecmnet.html>).  Both 
reports noted an objective of finding a prime factor of 60-digits or 
more.  The present jump of 7-digits in the record factor size may be 
compared with a 4-digit jump that occurred for the first factor with 
50-digits or more (from 49- to 53-digits, using a cluster of pentium
IV chips, 1998).  A second, more reasonably sized factor, with 62-digits
was found four days later (April 6 and April 10).  A third large factor,
64-digits, from the 1030-bit repunit R311, was just reported by 
Aoki-Shimoyama (Sept 5th).

The 59-digit record report noted using improved hardware, 2Gb Ram,
for the memory intensive step 2 (recalled in [D]), substantially 
improved in the new version of the software.  We recall that the 
method searches for elliptic curves (mod p, for the unknown prime 
factor) having an order with all but (at most) one prime factor below
a 1st-step bound B1, with largest factor of the elliptic curve order 
below a 2nd-step bound B2. The new factors (66- and 62-digits) were 
found making use of Torbjorn Granlund's 64-bit AMD assembly 
development code for the multiple precision package GMP (on which 
GMP-ECM is built) on a cluster of 120 1.8 Ghz Opteron chips.  This 
code gave a full factor of two off of the runtime in both step 1 and
step 2.  

The previous record used B1 = 260M (260e6), optimized for finding
60-digit factors.  After a hard run of 25,000 curves with B1=260M 
produced no factors at all, the new record was set early in a run 
of over 250,000 curves with B1 = 110M (optimal for 55-digit factors)
on larger, less tested numbers.  The record curve for the 66-digit 
factor has an un-usually smooth order, particularly the size of the
step 2 factor, as specified below.

The Opteron cluster used was purchased by a Major Research 
Instrumentation grant from NFS.  All jobs were run using Condor at 
lowest priority.  Paul Zimmermann has provided exceptional suport.

-Bruce Dodson, Math Dept, Lehigh University

[D]  301-digit integer factored: ecm record 57-digit factor, Dodson,
NmbrThry listserv, July 2003. (//www.lehigh.edu/~bad0/p57)
[Z]  new ECM record (59 digits) and GMP-ECM release (6.0), Zimmermann,
NmbrThry listserv, March 2005. (//www.loria.fr/~zimmerma/records/p59)
---------------------
p66 curve order:

p66 = 709601635082267320966424084955776789770864725643996885415676682297
curve defined by sigma = 1875377824 (see [D]; random selection by program)

order product of

   4*3 * 11243*336181*844957 (small factors, < 10^6)
   1866679*6062029*7600843*8046121*8154571*13153633 (medium factors, <B1)
      249436823 (large factor, 249e6, between B1, B2)

found in 180-digit cofactor of 3^466+1, leaving prime cofactor, 114-digits
------------------
p62 curve order:

p62 = 31069150378873790895208046895771360949463293546412105951449429
curve defined by sigma = 1507467457 (random)

order product of

   64 * 3*5*7 * 743*6143*66041*698311 ( < 10^6)
   2253259 * 21053117 * 28982407 * 40945981 ( < B1)
     390171012887 (large, step 2 factor, 390e9, between B1, B2)

found in 187-digit cofactor of 2^2034+1, leaving prime cofactor, 126-digits
-----------------
addendum 1:  Aoki-Shimoyama p64 curve order

p64 = 4344673058714954477761314793437392900672885445361103905548950933
curve defined by sigma = 1917732841

order product of

   128* 3*5*11 * 37*251*620623  ( < 10^6)
   2673137*9876511*20013391*35074997*159860663 ( < B1 =850M, 65-digit optimal)
     481875853859 (large, step 2 factor, 481e9, between B1, B2)

found in 311-digit repunit R311 = (10^311-1)/9 = p64 * 247-digit_prime,
formerly a leading candidate for the first 1024-bit SNFS factorization.
--------------
addendum 2:  The current largest group order factor is 14730236612879,
14e12, found in an Opteron curve over a 45-digit prime factor of 2^1091-1
= M1091, with first step bound 110e6 and sigma=2553734912.