mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2007-05-15, 05:49   #1
yqiang
 
Apr 2007

3 Posts
Default gmp-ecm 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 gmp-ecm 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
yqiang is offline   Reply With Quote
Old 2007-05-15, 13:28   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by yqiang View Post
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 gmp-ecm to factor 2^600+1 which yielded a prime factor of 88 digits,

<No, it did not. I am sure ECM found smaller factors. The last cofactor
just happened to be a large prime.>



Obviously the last factor found was found trivially after splitting off all the previous factors.

<Obviously!>


Yi

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^n-1 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.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-16, 13:02   #3
Jens K Andersen
 
Jens K Andersen's Avatar
 
Feb 2006
Denmark

2·5·23 Posts
Default

Quote:
Originally Posted by yqiang View Post
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?
If a number is completely factored then the largest factor does not count. When GMP-ECM finds a factor, it performs a prp test on the factor and cofactor (the number obtained by dividing the original number by known factors). The ecm method is not used to make prp tests.
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^a-1 and 2^b-1 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 GMP-ECM on each algebraic factor instead of the original number.

The largest prp cofactor which was found with GMP-ECM 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.
Jens K Andersen is offline   Reply With Quote
Old 2007-05-16, 13:51   #4
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

But what about a case such as 123012031 ?

which is 4523 * 27197

Depending on the sigma I can discover either factor:-

GMP-ECM 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

GMP-ECM 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
Greenbank is offline   Reply With Quote
Old 2007-05-16, 16:16   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142628 Posts
Default

That's a case which runs into Brent's rule, whose intent is that using ECM for longer than the expected runtime of a guaranteed-success 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 sixty-digit 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]
fivemack is offline   Reply With Quote
Old 2007-05-18, 09:15   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46408 Posts
Default

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/top10-2003.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
akruppa is offline   Reply With Quote
Old 2007-05-18, 12:23   #7
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

9A716 Posts
Default

Quote:
Originally Posted by akruppa View Post
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/top10-2003.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
Yes, but this factor was found with B1 ~ 3.9M (!) (just above p40-optimal), so I guess it was propably not over-ecm'd.

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 ECM-record?

Last fiddled with by Andi47 on 2007-05-18 at 12:26
Andi47 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question from Quora.com web site page Raman Puzzles 1 2016-09-20 02:36
Question re: Benchmarks Page Rodrigo Hardware 44 2011-07-01 21:55
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Question about your page OmbooHankvald 15k Search 2 2005-08-02 14:53
Records in January wblipp ElevenSmooth 10 2004-03-22 01:26

All times are UTC. The time now is 19:27.

Fri Oct 30 19:27:44 UTC 2020 up 50 days, 16:38, 2 users, load averages: 1.39, 1.74, 1.94

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.