Skip
repetitive navigational links
L-Soft  -  Home of  the  LISTSERV  mailing list  manager LISTSERV(R) 14.4
Skip repetitive navigational links
Previous messageNext messagePrevious in topicNext in topicPrevious by same authorNext by same authorPrevious page (September 2005)Back to main NMBRTHRY pageJoin or leave NMBRTHRYReplyPost a new messageSearchProportional fontNon-proportional fontLog out
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 (<http://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. (http://www.lehigh.edu/~bad0/p57) [Z] new ECM record (59 digits) and GMP-ECM release (6.0), Zimmermann, NmbrThry listserv, March 2005. (http://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.


Back to: Top of message | Previous page | Main NMBRTHRY page

LISTSERV.NODAK.EDU CataList email list search Powered by LISTSERV email list manager