mersenneforum.org gmp-ecm records page question
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-15, 05:49 #1 yqiang   Apr 2007 3 Posts 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
2007-05-15, 13:28   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010110002 Posts

Quote:
 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, Obviously the last factor found was found trivially after splitting off all the previous factors. 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.

2007-05-16, 13:02   #3
Jens K Andersen

Feb 2006
Denmark

E616 Posts

Quote:
 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.

 2007-05-16, 13:51 #4 Greenbank     Jul 2005 2×193 Posts 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
 2007-05-16, 16:16 #5 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×7×461 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 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]
 2007-05-18, 09:15 #6 akruppa     "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/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
2007-05-18, 12:23   #7
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 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?

Last fiddled with by Andi47 on 2007-05-18 at 12:26

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Puzzles 1 2016-09-20 02:36 Rodrigo Hardware 44 2011-07-01 21:55 Brian-E Math 25 2009-12-16 21:40 OmbooHankvald 15k Search 2 2005-08-02 14:53 wblipp ElevenSmooth 10 2004-03-22 01:26

All times are UTC. The time now is 10:58.

Tue Mar 28 10:58:05 UTC 2023 up 222 days, 8:26, 0 users, load averages: 0.88, 0.71, 0.69

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔