About M1277

[rudy235]

Originally Posted by chalsall

Just between you and me (and everyone else reading this), it is OK to be dyslexic. Almost all are, but just don't yet realize it.

Being "on the spectrum" is actually nominal. Very few people are actually "normal".

It took me a very long time to figure this out.

Sincerely.

Very much appreciated!

[chalsall]

Originally Posted by rudy235

Very much appreciated!

Thanks. This is cathartic for me as well.

[storm5510]

Originally Posted by chalsall

...Being "on the spectrum" is actually nominal. Very few people are actually "normal".

It took me a very long time to figure this out.

Sincerely.

It also took me a very long time. Those here who used the fact like a cattle prod now exist in my "ignore list."

[PhilF]

Originally Posted by chalsall

Almost all are, but just don't yet realize it.

I pardon your beg?

[xilman]

Originally Posted by chalsall

Very few people are actually "normal".

We are normal and we demand our freedom.

[storm5510]

I just looked at M1277's history on Primenet. It is extensive. There are entries as recent as yesterday. Lots of assigned ECM's. There are a lot of P-1 tests too. One that caught my eye had a B2 value which was 21 digits in length. I imagine that took some time to run. I don't know if this could be done with gpuOwl or not.

It's current TF level is 2^68. mfaktc won't accept it. Too small, it says. It's minimum is 100e3. One of the older versions might but there would probably be hardware compatibly problems with the drivers. The only program I know for a fact that could run it is Factor5. It's a dinosaur and the slowest of the slow. It's last update was in 2009.

[kriesel]

Originally Posted by storm5510

There are a lot of P-1 tests too. One that caught my eye had a B2 value which was 21 digits in length. I imagine that took some time to run. I don't know if this could be done with gpuOwl or not.

It's current TF level is 2^68. mfaktc won't accept it. Too small, it says. It's minimum is 100e3. One of the older versions might but there would probably be hardware compatibly problems with the drivers. The only program I know for a fact that could run it is Factor5.

As I recall there are special versions of mfaktx for small exponents. I don't know if they go as low as needed though. Mfactor could run it, and is faster than Factor5.
P-1 on gpuowl is very unlikely for such a small exponent. A very small fft length would be needed; at ~2-20 bits/word, ~640 to 64 words fft length. The smallest fft lengths ever seen implemented in gpuowl were 8K words and up, in v6.5 to V6.10. It's also doubtful that gpuowl handles B2 values so large. 2⁶⁴ ~10^19.2.

Mfactor on M1277, timed on one thread on I5-1035G1 (4 core / 8 HT), Windows 10, prime95 paused, usual interactive use:

40-41 bits, 2.16 seconds elapsed, 1.358 seconds Mfactor timing:
at Sat 06/04/2022 14:41:58.20 mfactor-base-1w -m 1277 -bmin 40 -bmax 41
done at Sat 06/04/2022 14:42:00.36
(not enough time resolution, probably biased by startup times, try again deeper)

50-51 bits:
at Sat 06/04/2022 14:42:46.25 mfactor-base-1w -m 1277 -bmin 50 -bmax 51
done at Sat 06/04/2022 15:08:21.46
duration 25:35.21 ~0.4264 hours elapsed (25.34.510 Mfactor timing)

67-68 extrapolated, one thread: 2^17 = 131072. times 50-51 time = 55895. hours (6.38 years single threaded)
extrapolated to 8 hyperthreads on this CPU, no better than 8:1 ideally; 0.798 years; could do better with a 16-thread or 16-core CPU.

Splitting M1277 TF from 68-69 bits to run many passes in parallel spread over multiple systems
using the more-classes version of Mfactor is possible.
That would allow ~960-fold speedup over single-threaded, given enough total CPU cores to run a pass on each.
Actually a little better than that, since the many-classes version eliminates more factor candidates from consideration early via a bigger wheel sieve.
Instead of 16 of 60 classes, it uses 960 of 4620 classes, so might be faster by up to ~ 16/60 / (960/4620) = 0.266667 / 0.207792 = 1.28333 x.
So for similar speed per thread or core, max parallelism (960 threads), ~ 1.9 days for 67-68 bits, ~3.8 days for 68-69.
That's ~9.94 core-years for an estimated ~1.45% chance of finding a factor (without considering how prior P-1 and ECM would have already covered some trial candidates, therefore reducing odds of finding a factor by trial factoring after the copious/deep P-1 and ECM).

[VBCurtis]

Originally Posted by kriesel

.... (without considering how prior P-1 and ECM would have already covered some trial candidates, therefore reducing odds of finding a factor by trial factoring after the copious/deep P-1 and ECM).

Anyone who considers TF on M1277 is assigned the task of determining how much ECM has been run, as it applies to the chances of a factor remaining below some bit level far far out of reach of TF- say, 100 bits.

I guarantee that more than 3 * t65 of ECM has been run. Given this, what are the odds of a factor below 100 bits? 120 bits? 150 bits?

The only correct answer to any commentary pondering TF on M1277 is "you are wasting your time". But Ken likes to write essays about such things, so perhaps he will do so for this assignment as well.

[storm5510]

Originally Posted by kriesel

As I recall there are special versions of mfaktx for small exponents. I don't know if they go as low as needed though. Mfactor could run it, and is faster than Factor5.
P-1 on gpuowl is very unlikely for such a small exponent. A very small fft length would be needed; at ~2-20 bits/word, ~640 to 64 words fft length. The smallest fft lengths ever seen implemented in gpuowl were 8K words and up, in v6.5 to V6.10. It's also doubtful that gpuowl handles B2 values so large. 2⁶⁴ ~10^19.2.

Mfactor on M1277, timed on one thread on I5-1035G1 (4 core / 8 HT), Windows 10, prime95 paused, usual interactive use:

Mfactor is a new one on me. I've never read about it before.

Somebody, I do not remember who, believed a factor for M1277 could be found somewhere above 1e15.

At the present, this is just too much time. I wonder if Google's quantum setup could do something like this?

[chris2be8]

Look at what P-1 bounds have been done before starting TF. P-1 is sure to find any factor smaller than B1, and almost sure to find any factor smaller than min(B1^2, B2) (there's only a very rare case it could miss). So running TF to less than the largest P-1 B1 is certainly pointless.

And with ECM run to 3*T65 there are unlikely to be any factors less than 65 *decimal* digits. So *very* unlikely to be any in reach of TF.

[kriesel]

With such a cordial invitation from VBCurtis, how could anyone resist.

My previous post in this thread was partly about feasibility of further TF on M1277, and not about the utility (or utility per unit effort) or lack of utility of such an attempt. Even the lowest step in the learning curve would not have fit in that one-hour edit window.


Comparing info for the various factoring methods on M1277 at https://www.mersenne.ca/exponent/1277

Although many have been repeated to lesser TF levels or P-1 bounds, if the initial runs are performed correctly, there is no point in repeating deterministic factoring. Normally GIMPS does not DC factoring, when error rates are low enough.

TF:
deterministic, already completed up to 2^68; total of 46,675.7 GHD previously expended excluding duplications, corresponding to ~20. CPU-core-years in Mfactor. Effort is exponential with bit level.
TF tries all (presieved) factor candidates in an interval, often 2^(b-1) to 2^b. P-1 finds factors f = 2 k p + 1 with smooth k. There is an estimated ~20% overlap of P-1 in what TF has already covered for usual factoring.
Commonly used first in GIMPS wavefront testing, up to a chosen optimal effort bit level.
Pointless to continue further on M1277 IMO

P-1:
deterministic, already completed up to assorted bounds combinations, including these 2 largest B2 and B1 respectively:
B1= 777,777,777,777 (~7.78E11) B2 2,038,915,387,344,735,900 (~2E18) (41.85% chance) 2,626,424. GHD
B1 5,000,000,000,003 B2 400,000,000,000,241 (29.4% chance, 627. GHD)
If we suppose the k value of a hypothetical factor had 3 factors < B1 and 1 at ~B2/2, these would be ~ 17 359 42,000,000,000 1E18 ~ 119 bits, so f = 2kp+1 would have ~130 bits.
The current record largest P-1 factor found for Mersenne numbers is 181 bits, per https://www.mersenne.ca/userfactors/pm1/1/bits
Commonly used on survivors of TF, ideally once to bounds computed as providing optimal probable savings of total compute time considering primality testing avoided by finding a factor.
Pointless to continue further on M1277 IMO

P+1:
(half the time it's really P-1) Not regarded as beneficial for GIMPS wavefront factoring before primality testing, per George Woltman, but can be useful for small exponents.
start 2/7 B1 100,000,000,000 B2 10,000,000,000,000 16 GHD
B1 1,000,000,000,000 35 GHD
start 6/5 B1 100,000,000,000 B2 10,000,000,000,000
B1 1,000,000,000,000
start random: none
Largest factor of a Mersenne number yet found by P+1 is 120 bits per https://www.mersenne.ca/userfactors/pp1/1/bits
Pointless to continue further on M1277 IMO

ECM:
Not regarded as beneficial for GIMPS wavefront factoring before primality testing.
Not deterministic in usual use; many curves are run, each for different randomly selected sigma for a set of bounds. Based on old calculation method table:
~9,173,061 GHD, ~0 chance 50 digit (~166 bit) factor or smaller missed; <1% chance <55 digit (~183 bit) missed; 13% 60 digit (~199 bits); ~56% chance ~65 digit (~216 bit) factor missed
The new calculation method appears to indicate lower odds of missed factors for the same digits (bits) level; 0.001% at 60 digit (~199 bits); no data given for higher.
See also https://www.mersenne.org/report_ecm/
https://www.mersenne.ca/exponent/1277 shows a computed t level of 62.878 for both old and new calculation method tables.
I'm not sure how all that compares to VBCurtis' guarantee of > 3 * t65 of ECM on M1277 in https://mersenneforum.org/showpost.p...7&postcount=19. (What is t65?)
Readers as unfamiliar with ECM as I am (haven't used it in years, or coded it ever) may find these interesting:
https://mersenneforum.org/showpost.p...postcount=1922
https://mersenneforum.org/showthread.php?t=24113
https://en.wikipedia.org/wiki/Lenstr..._factorization
https://www.alpertron.com.ar/ECM.HTM (Factoring using the Elliptic Curve Method) explains the bounds
Per https://mersenneforum.org/showthread.php?t=24897 running the recommended number of curves for specific bounds reduces the chance of a missed factor by 1/e.
Largest known factor listed as found by ECM for a Mersenne number is 73 digits (240 bits) for M1181, #16 of https://members.loria.fr/PZimmermann/records/top50.html
which would have taken ~1.4E14 GHD by TF to find, using perhaps Factor5. https://www.mersenne.ca/exponent/1181
ECM has already reached far deeper than TF, P-1, or P+1.
I estimate the indicated effort already expended corresponds to ~3900. CPU-core-years.

SNFS:
per https://mersenneforum.org/showpost.p...17&postcount=5 could be attempted with sufficient resources, up to 1-1.5 TB RAM;
https://mersenneforum.org/showpost.p...36&postcount=9 states requiring of order 10,000 CPU-years.
Largest known factor found for a Mersenne number by nfs is 483 bits for M1109 per https://www.mersenne.ca/userfactors/nfs/1/bits
I know even less about NFS than ECM, but the sharing of some sieving cost across multiple targets to be factored providing a >2:1 throughput improvement is interesting in https://eprint.iacr.org/2014/653.pdf
How many of the performance improvements mentioned in that article have made it into freely available NFS software I do not know.
Images of GGNFS at https://download.mersenne.ca/GGNFS are from 2020. Description at https://www.math.ttu.edu/~cmonico/software/ggnfs/ indicates larger than 140-160 digits involves issues with bugs.
Perhaps Ben Delo will take an interest in M1277 factorization someday.

Other?
Do any other potential factoring methods belong in this list regarding M1277 or similar sized unfactored Mersennes?