20070515, 05:49  #1 
Apr 2007
3 Posts 
gmpecm records page question
Hello,
I apologize if this question is utterly stupid, but I was not able to find a FAQ for this anywhere. I am confused about the records on http://www.loria.fr/~zimmerma/records/ecmnet.html For example, it lists a prime factor of (78,129) but it does not give the complete factorization of it. Does this mean that someone just split off that particular factor, while the rest is unknown? How do you determine that the rest is not a product of small primes (trial division up to a limit)? What are the guidelines for submitting records? For example, I used gmpecm to factor 2^600+1 which yielded a prime factor of 88 digits, I have a feeling that it is not a record because the factorization is: [82471201, 394783681, 4278255361, 46908728641, 182241312541857662739617, 432363203127002885506543172618401, 8059720126266442627050052102446681278605043839701907629253987599434464819580116421853601] Obviously the last factor found was found trivially after splitting off all the previous factors. Cheers, Yi 
20070515, 13:28  #2  
Nov 2003
16444_{8} Posts 
Quote:
People run ECM on composite numbers that have already had their small factors removed. Richard Brent keeps track of factorizations of a^n + 1 and a^n1 for a > 12 on his website. One can find known small factors there. The factorization of 2^600+1 was first found a LONG time ago. I suggest that you consult the already published tables before burning more CPU cycles. 

20070516, 13:02  #3  
Feb 2006
Denmark
11100110_{2} Posts 
Quote:
If the factor or cofactor is prp then another program, for example Primo or PARI/GP, must be used to prove that it is really prime. Also note that some numbers of special forms have "algebraic factors" or similar. This is divisors which are known in advance because of the form of the number. For example, 2^a1 and 2^b1 divides 2^(a*b)1. The largest prime factor of an algebraic factor does not count in ecm records. Actually, it is highly recommended (much faster) to run GMPECM on each algebraic factor instead of the original number. The largest prp cofactor which was found with GMPECM and later proved prime may be Fibonacci(30671)/1141737296775689 with 6395 digits, proved by Primo. Larger unproved prp cofactors are known. If the cofactor is smaller than the factor found by ecm, then some have allowed the factor in ecm records. On the other hand, http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt disallows any factor which even comes close to the cofactor in size. 

20070516, 13:51  #4 
Jul 2005
602_{8} Posts 
But what about a case such as 123012031 ?
which is 4523 * 27197 Depending on the sigma I can discover either factor: GMPECM 6.1 [powered by GMP 4.1.4] [ECM] Input number is 123012031 (9 digits) Using B1=100, B2=2046, polynomial x^1, sigma=3741624400 Step 1 took 0ms ********** Factor found in step 1: 4523 Found probable prime factor of 4 digits: 4523 Probable prime cofactor 27197 has 5 digits GMPECM 6.1 [powered by GMP 4.1.4] [ECM] Input number is 123012031 (9 digits) Using B1=100, B2=2046, polynomial x^1, sigma=3887925014 Step 1 took 0ms ********** Factor found in step 1: 27197 Found probable prime factor of 5 digits: 27197 Probable prime cofactor 4523 has 4 digits 
20070516, 16:16  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
1100011101110_{2} Posts 
That's a case which runs into Brent's rule, whose intent is that using ECM for longer than the expected runtime of a guaranteedsuccess method is a waste of computrons not to be rewarded.
[ie, if you have a C120=P60*P60, you factor it by GNFS and it takes 80 hours; you don't bother running the thousands of hours of ECM needed to get a sixtydigit factor. If you have a C180 which is susceptible to SNFS, it's daft to run ECM for longer than the 80 or so hours that the SNFS run would take] 
20070518, 09:15  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
There was a case where a prime factor bigger than the cofactor was found and made the #1 spot on Paul Zimmermann's TOP10 list of that year, see http://www.loria.fr/%7Ezimmerma/records/top102003.html
There was a bit of discussion following the discovery about what is and what isn't an ECM champion, and as a result, Brent introduced the r / r' > 2.2 rule. Alex 
20070518, 12:23  #7  
Oct 2004
Austria
2·17·73 Posts 
Quote:
What if somebody would find a lucky p70 as a factor of a c140 with a few curves at B1 <= 3M? Would this not be considered an ECMrecord? Last fiddled with by Andi47 on 20070518 at 12:26 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Question from Quora.com web site page  Raman  Puzzles  1  20160920 02:36 
Question re: Benchmarks Page  Rodrigo  Hardware  44  20110701 21:55 
Records for complete factorisation  BrianE  Math  25  20091216 21:40 
Question about your page  OmbooHankvald  15k Search  2  20050802 14:53 
Records in January  wblipp  ElevenSmooth  10  20040322 01:26 