Help factoring M127^k-1

[swellman]

Originally Posted by swellman

I’m finishing up C142_M31_c38 now.

The C142 is now factored, though someone found a p25 before I finished. The remains p56 and p62 were reported to fdb.

[fivemack]

Completed 8960@260e6 on C291_M127_k30 without a factor

[fivemack]

167434826987225560414010881210279 divides C271_M31_k29 and that completes the factorisation

[pinhodecarlos]

Someone factored C149_M31_k54.

http://factordb.com/index.php?query=71616377109907864688008347908682359177816201466974857346197413741355050473949229228608329211063362973255861812104220291663736034427872242744908822221

[kosta]

p258550963755000298476185095462811 divides M127_k71, but
sadly the cofactor is composite. I am going to try to continue, but not for now.
Request:
The following need more curves at 1e7, you can run a few hundred curves, without reserving but please report afterward:

k=41 : C1480 : polcyclo(41, M127) /8654875813 /17533681649071904078998695327717677700319
k=55 : C1494 : polcyclo(55, M127) /277793918294958165761 /2105998294816571
k=53 : C1939 : polcyclo(53, M127) /18390188112327039068872972462423220606095920579379
k=103: C3848 : polcyclo(103, M127) /1587438804691 /51238052714332339 /376939256820458362494193
k=107: C4040 : polcyclo(107, M127) /12603321121663

and, these at 1e8, imho, a few hundred curves is good enough to have confidence that there are no more factors less than 50 digits

k=29: C1064 : polcyclo(29, M127) /26896979
k=59: C2218 : polcyclo(59, M127)
k=61: C2237 : polcyclo(61, M127) /5214037913900890243433103953190842218238921096763811372153

[fivemack]

Originally Posted by kosta

and, these at 1e8, imho, a few hundred curves is good enough to have confidence that there are no more factors less than 50 digits

I'm not quite sure why you disagree by such a large factor with gmp-ecm:

Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
35      141     650     3366    19370   122360  840072  6217999 4.9e+07 4.1e+08

so I would want 10,000 curves at 1e8 to have confidence at the 5% = exp(-3) level of no factors less than 50 digits.

On a not-very-fast machine (1 core of 2.6GHz Ivy Bridge), one curve at 1e8 takes 5GB of memory and about three and a quarter hours, so 10k curves at 1e8 is comparable effort to factorising a C180 by GNFS.

[fivemack]

2048167920754497417103998099314569059259651387 divides M7^123-1

[kosta]

@fivemack:
The 3366 curves from that table will give you exp(-1) probability, so a few hundred curves will not give you "confidence" , you are right about that.

But there is something else. When we find a factor of D-digits in some number and the cofactor is composite, what is the expectation value of the number of digits for the next factor? I dont know of any mathematical theorem to that effect, but simple heuristic based on randomness of residues tells me, the next factor will have 2*D digits on average. I actually downloaded a bunch of tables from factordb and plotted the statistics. The result is that among factors already discovered each is on average 1.5-2 times longer than the previous one. Also, it is immediately clear from my plots, once you found a 35 digit factor, there is a high probability (>50%) you will never find another one with ECM.

The conclusion? It is a waste to take the standard "Optimal Parameters" table and run all the curves on each line, as the steps are at 5-digit intervals. The optimal parameters table is calculated correctly, of course, but it gives you the optimal figure to find a factor IF it exists. Not knowing the next factors size, the strategy is suboptimal, by wasting ~5% of computing power according to my estimates. Its not alot, but it is something. Optimal strategy might be:
1) run all the curves, but double the number of digits you look for at each step.
2) run less, much less curves, and increase B1 gradually as in the tables.
obviously, people will not like 1) as it will mean giving up at 30-35 digits. My request for a few hundered curves was in the spirit of 2).

[henryzz]

Originally Posted by kosta

@fivemack:
The 3366 curves from that table will give you exp(-1) probability, so a few hundred curves will not give you "confidence" , you are right about that.

But there is something else. When we find a factor of D-digits in some number and the cofactor is composite, what is the expectation value of the number of digits for the next factor? I dont know of any mathematical theorem to that effect, but simple heuristic based on randomness of residues tells me, the next factor will have 2*D digits on average. I actually downloaded a bunch of tables from factordb and plotted the statistics. The result is that among factors already discovered each is on average 1.5-2 times longer than the previous one. Also, it is immediately clear from my plots, once you found a 35 digit factor, there is a high probability (>50%) you will never find another one with ECM.

The conclusion? It is a waste to take the standard "Optimal Parameters" table and run all the curves on each line, as the steps are at 5-digit intervals. The optimal parameters table is calculated correctly, of course, but it gives you the optimal figure to find a factor IF it exists. Not knowing the next factors size, the strategy is suboptimal, by wasting ~5% of computing power according to my estimates. Its not alot, but it is something. Optimal strategy might be:
1) run all the curves, but double the number of digits you look for at each step.
2) run less, much less curves, and increase B1 gradually as in the tables.
obviously, people will not like 1) as it will mean giving up at 30-35 digits. My request for a few hundered curves was in the spirit of 2).

Try http://mersenneforum.org/showthread.php?t=21420

[henryzz]

Originally Posted by henryzz

Try http://mersenneforum.org/showthread.php?t=21420

Further to above RDS suggested you should read: https://www.jstor.org/stable/2152967?seq=1

Originally Posted by RDS

If one finds a factor D of a much larger number, then
the next expected factor (ordered by size) is D^e.
i.e. the size of the next factor is e*size(D). This may
be derived from the Erdos-Kac theorem by considering
order statistics of a normal random variable.

[pinhodecarlos]

Originally Posted by henryzz

Further to above RDS suggested you should read: https://www.jstor.org/stable/2152967?seq=1

I've got that paper with me in case someone wants to read it in pdf.