gmp-ecm records page question

[yqiang]

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

[R.D. Silverman]

Originally Posted by yqiang

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.

[Jens K Andersen]

Originally Posted by yqiang

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.

[Greenbank]

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

[fivemack]

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]

[akruppa]

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

[Andi47]

Originally Posted by akruppa

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?