...merely a question about ECM world record?

[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.

[xilman]

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.

[ewmayer]

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?

[lukerichards]

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.

[Batalov]

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).

[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.

[lukerichards]

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".

[kriesel]

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.

[retina]

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.

[DukeBG]

lukerichards,

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.

[Dr Sardonicus]

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.