mersenneforum.org ...merely a question about ECM world record?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-03-18, 17:54 #1 lukerichards     "Luke Richards" Jan 2018 Birmingham, UK 25·32 Posts ...merely a question about ECM world record? A quick Google and a read of the Wikipedia page for ECM factoring list the all time record factor found by ECM at 83 decimal digits long, a 2013 record. Is this 'fact' up to date? Does the record have to be a prime? I ask because today I used the ECM function on Prime95 to find a 106 digit long composite factor of a 240,000 digit number.
2019-03-18, 18:07   #2
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·5,791 Posts

Quote:
 Originally Posted by lukerichards Is this 'fact' up to date? Does the record have to be a prime?
As far as I know, and yes respectively.

Nonetheless you may wish to drop an email to PaulZ.

2019-03-18, 18:38   #3
ewmayer
2ω=0

Sep 2002
Repรบblica de California

1175410 Posts

Quote:
 Originally Posted by lukerichards A quick Google and a read of the Wikipedia page for ECM factoring list the all time record factor found by ECM at 83 decimal digits long, a 2013 record. Is this 'fact' up to date? Does the record have to be a prime? I ask because today I used the ECM function on Prime95 to find a 106 digit long composite factor of a 240,000 digit number.
106 digits is meaningless - only any previously unknown prime factors in there matter. What is the factorization of your c106, and did you check the largest prime factors against known factors of the c240000, if any such tabulation exists?

2019-03-18, 19:55   #4
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts

Quote:
 Originally Posted by ewmayer 106 digits is meaningless - only any previously unknown prime factors in there matter. What is the factorization of your c106, and did you check the largest prime factors against known factors of the c240000, if any such tabulation exists?

Hi ewmayer. I'm assuming you didn't mean to come across quite so brusquely, but your tone is a little off-putting here.

No, I didn't. The websites I saw which list the records give no indication of a requirement for the factors to be prime, nor to have been previously undiscovered. They merely state that they are showing the largest factors found using ECM methods. After all, the algorithm does not know that the factors are in a table of known factors.

But I think what was clear from the replies of others, is that there was (as I suspected) more to it than just finding a factor, rendering this quite unwelcoming and accusatory response somewhat unnecessary.

 2019-03-18, 21:31 #5 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 7×1,427 Posts Many people have found very large composite factors with ECM. It is very easy to construct an input such that the ECM factor will be enormous (>>106 digits).
 2019-03-18, 21:56 #6 ewmayer ∂2ω=0     Sep 2002 Repรบblica de California 2DEA16 Posts Didn't mean to off-put anyone, just pressed for time and "understanding the occurrence of composite factors is a really basic part of using such factoring algorithms". If you want to claim a record in the 100m sprint, you surely understand you don't start the race from the 90m mark. If saying so makes me 'brusque', so be it.
2019-03-18, 22:01   #7
lukerichards

"Luke Richards"
Jan 2018
Birmingham, UK

4408 Posts

Quote:
 Originally Posted by ewmayer Didn't mean to off-put anyone, just pressed for time and "understanding the occurrence of composite factors is a really basic part of using such factoring algorithms". If you want to claim a record in the 100m sprint, you surely understand you don't start the race from the 90m mark. If saying so makes me 'brusque', so be it.

Clue is in the name really... "100m sprint"

So really "largest factor found by ECM" should be called "largest undiscovered prime factor found by ECM". Otherwise its akin to calling it "First person to cross the finish line" rather than "100m sprint".

 2019-03-18, 22:44 #8 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 23×7×127 Posts Communication is hard. What A means-> what A says or writes -> What B hears or reads -> What B interprets it to mean. Most of in-person communicatioin is nonverbal. Here, there's no smile or nod or other gesture to show that A means it in a friendly helpful way. If B was excited about something, then disappointed, it's easy to perceive negativity where none's meant or perhaps where none's objectively present. Closing the loop helps. B states his interpretation. A responds, not exactly what I meant; (clarification follows). Different styles/cultures can complicate it. On another note, 106 digits is around 352 bits. Larger composite factors are known. Consider an assortment of partially factored Mersenne numbers with several prime factors, totaling 400-650 bits per number. https://www.mersenne.ca/manyfactors.php Factoring for GIMPS sometimes produces composite factors. The Primenet server checks the reported factors for whether they are composite, and whether they are actual factors of the Mersenne number; errors do occur. A list of prime factors is much more succinct than a list of the prime factors plus all composite combinations of them. Last fiddled with by kriesel on 2019-03-18 at 22:46
2019-03-18, 22:56   #9
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

29·229 Posts

Quote:
 Originally Posted by lukerichards I ask because today I used the ECM function on Prime95 to find a 106 digit long composite factor of a 240,000 digit number.
Nobody cares about composite factors. Give the prime factors, that is all that matters.

2019-03-19, 09:13   #10
DukeBG

Mar 2018

3×43 Posts

lukerichards,

Quote:
 d:\primes\gmpecm-svn3027-skylake>echo 2^^^^5040-1 | ecm 1e5 GMP-ECM 7.0.5-dev [configured with GMP 6.1.2, --enable-asm-redc] [ECM] Input number is 2^5040-1 (1518 digits) Using B1=100000, B2=35857930, polynomial x^2, sigma=0:6058314822046302847 Step 1 took 3093ms ********** Factor found in step 1: 17207364497321500452486476456002233250196903814518726713630576551 4079163048902492088730743911280872589684294662075988282315778821629635993710157532896874444944623853 3747698578718573768108194953550610233408983168489066441394188039436933504421027020831366100332571798 1280683235451769107287417452200736950816750375105591848143504606274123769646693506143808582814902744 4977066838425 Found composite factor of 378 digits: 17207364497321500452486476456002233250196903814518726713630576 5514079163048902492088730743911280872589684294662075988282315778821629635993710157532896874444944623 8533747698578718573768108194953550610233408983168489066441394188039436933504421027020831366100332571 7981280683235451769107287417452200736950816750375105591848143504606274123769646693506143808582814902 7444977066838425 Composite cofactor (2^5040-1)/1720736449732150045248647645600223325019690381451872671363057655140791 6304890249208873074391128087258968429466207598828231577882162963599371015753289687444494462385337476 9857871857376810819495355061023340898316848906644139418803943693350442102702083136610033257179812806 8323545176910728741745220073695081675037510559184814350460627412376964669350614380858281490274449770 66838425 has 1140 digits
You should probably learn a bit about how the method works. It's harder to find big primes, but finding big composites is as easy as finding the largest divisor in those composites, so to speak.

Last fiddled with by DukeBG on 2019-03-19 at 09:19

2019-03-19, 16:27   #11
Dr Sardonicus

Feb 2017
Nowhere

137248 Posts

Quote:
 Originally Posted by DukeBG lukerichards, You should probably learn a bit about how the method works. It's harder to find big primes, but finding big composites is as easy as finding the largest divisor in those composites, so to speak.
Nicely put. If you feed that 378-digit composite to Pari-GP's factor(), you'll see it busts up into a lot of really small factors.

Before siccing ECM onto a number, it's prudent to make sure there are no small factors.

With numbers of the form a^n - 1, a first whack is to bust it up into cyclotomic factors. Then, Aurefeuillian and intrinsic factors are low-hanging fruit. Then, you can strip out any small factors.

Just by way of practice, I did this with 2^5040 - 1. There weren't many composites left standing. They were all factors of the larger "primitive parts" (cyclotomic factors, with any intrinsic prime factor divided out).

Of course, with a = 2 and other small bases, this work (and a great deal more besides) has already been done. The remaining composites are listed in tables. Those would be your quarry for hunting with heavy artillery.

 Similar Threads Thread Thread Starter Forum Replies Last Post davieddy Operazione Doppi Mersennes 284 2021-10-24 13:53 Siegmund PrimeNet 6 2016-05-09 22:39 rogue Lounge 8 2012-03-02 16:41 R. Gerbicz Science & Technology 0 2010-07-28 01:50 jasong Factoring 0 2006-02-28 04:00

All times are UTC. The time now is 02:12.

Mon Dec 5 02:12:28 UTC 2022 up 108 days, 23:41, 0 users, load averages: 0.83, 0.84, 0.80