mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-06-03, 00:41   #12
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

2×5×113 Posts
Default

Quote:
Originally Posted by chalsall View Post
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!
rudy235 is offline   Reply With Quote
Old 2022-06-03, 00:50   #13
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·33·197 Posts
Default

Quote:
Originally Posted by rudy235 View Post
Very much appreciated!
Thanks. This is cathartic for me as well.

Last fiddled with by chalsall on 2022-06-03 at 00:53 Reason: Deleted true but inapproprite knowledge.
chalsall is offline   Reply With Quote
Old 2022-06-03, 22:17   #14
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

22·7·83 Posts
Default

Quote:
Originally Posted by chalsall View Post
...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."
storm5510 is offline   Reply With Quote
Old 2022-06-04, 16:29   #15
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

22·181 Posts
Default

Quote:
Originally Posted by chalsall View Post
Almost all are, but just don't yet realize it.
I pardon your beg?
PhilF is offline   Reply With Quote
Old 2022-06-04, 17:18   #16
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

11,483 Posts
Default

Quote:
Originally Posted by chalsall View Post
Very few people are actually "normal".
We are normal and we demand our freedom.
xilman is offline   Reply With Quote
Old 2022-06-04, 19:07   #17
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

22·7·83 Posts
Default

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.
storm5510 is offline   Reply With Quote
Old 2022-06-04, 19:30   #18
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

1A9A16 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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. 264 ~1019.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).

Last fiddled with by kriesel on 2022-06-04 at 20:27
kriesel is offline   Reply With Quote
Old 2022-06-04, 23:50   #19
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

5,471 Posts
Default

Quote:
Originally Posted by kriesel View Post
.... (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.
VBCurtis is offline   Reply With Quote
Old 2022-06-05, 15:01   #20
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
Not U. + S.A.

22×7×83 Posts
Default

Quote:
Originally Posted by kriesel View Post
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. 264 ~1019.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?
storm5510 is offline   Reply With Quote
Old 2022-06-05, 15:37   #21
chris2be8
 
chris2be8's Avatar
 
Sep 2009

95116 Posts
Default

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.
chris2be8 is offline   Reply With Quote
Old 2022-06-05, 18:19   #22
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

11010100110102 Posts
Default

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?
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Predict the number of digits from within the factor for M1277 sweety439 Cunningham Tables 7 2022-06-11 11:04
Python script for search for factors of M1277 using random k-intervals Viliam Furik Factoring 61 2020-10-23 11:52
M1277 - no factors below 2^65? DanielBamberger Data 17 2018-01-28 04:21

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


Sun Sep 25 07:19:49 UTC 2022 up 38 days, 4:48, 0 users, load averages: 0.84, 0.99, 1.05

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.

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