mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-03-18, 17:54   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default ...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.
lukerichards is offline   Reply With Quote
Old 2019-03-18, 18:07   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1142710 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
xilman is offline   Reply With Quote
Old 2019-03-18, 18:38   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

3·7·13·43 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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?
ewmayer is offline   Reply With Quote
Old 2019-03-18, 19:55   #4
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

12016 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
lukerichards is offline   Reply With Quote
Old 2019-03-18, 21:31   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

5×7×283 Posts
Default

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).
Batalov is offline   Reply With Quote
Old 2019-03-18, 21:56   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Repรบblica de California

3×7×13×43 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2019-03-18, 22:01   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25·32 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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".
lukerichards is offline   Reply With Quote
Old 2019-03-18, 22:44   #8
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

6,673 Posts
Default

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
kriesel is offline   Reply With Quote
Old 2019-03-18, 22:56   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11001101000102 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
retina is online now   Reply With Quote
Old 2019-03-19, 09:13   #10
DukeBG
 
Mar 2018

3×43 Posts
Default

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
DukeBG is offline   Reply With Quote
Old 2019-03-19, 16:27   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×7×211 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving freakishly big MMs (was "World record" phone number?) davieddy Operazione Doppi Mersennes 284 2021-10-24 13:53
World record sized double-check? Siegmund PrimeNet 6 2016-05-09 22:39
World Record Factorial Prime Found rogue Lounge 8 2012-03-02 16:41
70 billion pixels Budapest (world record) R. Gerbicz Science & Technology 0 2010-07-28 01:50
Question about record prime using Elliptical Curve method jasong Factoring 0 2006-02-28 04:00

All times are UTC. The time now is 07:24.


Tue Aug 16 07:24:35 UTC 2022 up 40 days, 2:11, 1 user, load averages: 0.76, 1.03, 1.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”