mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-09-11, 17:52   #100
Magellan3s
 
Mar 2022
Earth

5×23 Posts
Default

I'm pretty uninformed when it comes to this but.....

Is there a reason mfaktc can't be used? I know it has a minimum exponent size requirement but can that be changed?

Last fiddled with by Magellan3s on 2022-09-11 at 17:52
Magellan3s is offline   Reply With Quote
Old 2022-09-11, 18:22   #101
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·3·311 Posts
Default

Mfaktc is great at finding small factors but the miminal possible factor size of M1277 is many many orders of magnitude larger than anything it can find. We know this because of the amount of ECM completed on this number.

Last fiddled with by bsquared on 2022-09-11 at 18:25 Reason: Forgot the M
bsquared is offline   Reply With Quote
Old 2022-09-11, 18:38   #102
Magellan3s
 
Mar 2022
Earth

5×23 Posts
Default

Quote:
Originally Posted by bsquared View Post
Mfaktc is great at finding small factors but the miminal possible factor size of M1277 is many many orders of magnitude larger than anything it can find. We know this because of the amount of ECM completed on this number.
I think I understand, thank you!
Magellan3s is offline   Reply With Quote
Old 2022-09-11, 18:51   #103
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

1CC616 Posts
Default

Aside from the low-exponent issue, there's a limit in mfaktc at 95 bits, mfakto at 92 bits. M1277 has already been TF to 68 bits, and it took ~47,000 GHD. To go to 69 bits would take another ~47,000 GHD, which is ~3 weeks on an RTX2080 GPU. From 69-70 would take twice as long, 70-71 four times, etc., growing exponentially. Well before ~227 times 3 weeks, run time gets prohibitively long. And if not for that, from 95 bits to 1277/2 is beyond its current capability, requiring someone to code new kernels. https://www.mersenne.ca/exponent/1277
There's no multi-GPU implementation of TF for Mersenne numbers, so running a span of x to x+y bits, only parallelizes to 2 GPUs:
x to x+y-1 on GPU a, x+y-1 to x+y on GPU b, giving about equal run time for same model GPUs.
Some other possibilities were mentioned earlier in this thread https://mersenneforum.org/showpost.p...3&postcount=18
and VBCurtis responds that reachable TF is pointless because of the amount of ECM that has been done
https://mersenneforum.org/showpost.p...7&postcount=19
My attempted summary of factoring choices & past M1277 effort is https://mersenneforum.org/showpost.p...5&postcount=22 which indicates that almost any factors <166. bits would have already been found by ECM, so there's nothing reachable by TF remaining.
kriesel is offline   Reply With Quote
Old 2022-09-11, 19:09   #104
Magellan3s
 
Mar 2022
Earth

5·23 Posts
Default

Quote:
Originally Posted by kriesel View Post
Aside from the low-exponent issue, there's a limit in mfaktc at 95 bits, mfakto at 92 bits. M1277 has already been TF to 68 bits, and it took ~47,000 GHD. To go to 69 bits would take another ~47,000 GHD, which is ~3 weeks on an RTX2080 GPU. From 69-70 would take twice as long, 70-71 four times, etc., growing exponentially. Well before ~227 times 3 weeks, run time gets prohibitively long. And if not for that, from 95 bits to 1277/2 is beyond its current capability, requiring someone to code new kernels. https://www.mersenne.ca/exponent/1277
There's no multi-GPU implementation of TF for Mersenne numbers, so running a span of x to x+y bits, only parallelizes to 2 GPUs:
x to x+y-1 on GPU a, x+y-1 to x+y on GPU b, giving about equal run time for same model GPUs.
Some other possibilities were mentioned earlier in this thread https://mersenneforum.org/showpost.p...3&postcount=18
and VBCurtis responds that reachable TF is pointless because of the amount of ECM that has been done
https://mersenneforum.org/showpost.p...7&postcount=19
My attempted summary of factoring choices & past M1277 effort is https://mersenneforum.org/showpost.p...5&postcount=22 which indicates that almost any factors <166. bits would have already been found by ECM, so there's nothing reachable by TF remaining.
This cleared things up even more, thank you!
Magellan3s is offline   Reply With Quote
Old 2022-09-12, 09:15   #105
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3×23×149 Posts
Default

Quote:
Originally Posted by kriesel View Post
There's no multi-GPU implementation of TF for Mersenne numbers, so running a span of x to x+y bits, only parallelizes to 2 GPUs
Not my intention to contradict anything you (and other guys) said about the difficulty of such job, just want to point out that the TF can be easily paralelized to 960 GPUs (for the 4620 classes version) just by rewriting the checkpoint file of mfaktc, for example. Of course, writing a "parallel" version (where you can specify the class) is quite easy. However, this is futile, it will just shorter the time from (arbitrary) 900 million years to one million years
LaurV is offline   Reply With Quote
Old 2022-09-12, 12:12   #106
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·29·127 Posts
Default

Quote:
Originally Posted by LaurV View Post
TF can be easily paralelized to 960 GPUs (for the 4620 classes version) just by rewriting the checkpoint file of mfaktc, for example. Of course, writing a "parallel" version (where you can specify the class) is quite easy. However, this is futile, it will just shorter the time from (arbitrary) 900 million years to one million years
And require setting up a foundation (def'n 3b) to maintain the 1000 GPU farm including a few dozen hot spares for the long term. For NO factor-found utility, since ECM has already covered any reachable bit level. Ernst's Mfactor could be used in an analogous futile mass space heater game using CPUs, using existing code, and achieving even larger absurd run time estimates. And it allows specifying start and end k values, so each of the many classes could be subdivided for greater futile parallelism.

Last fiddled with by kriesel on 2022-09-12 at 13:04 Reason: apparently razzes are now required for certain posts. Some mods have no sense of humor, or misperceive that in others, or ?
kriesel is offline   Reply With Quote
Old 2022-09-12, 12:20   #107
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5·7·191 Posts
Default

Quote:
Originally Posted by kriesel View Post
And require setting up a foundation to maintain the 1000 GPU farm including a few dozen hot spares for the long term. For NO factor-found utility, since ECM has already covered any reachable bit level. Mfactor could be used in an analogous futile mass space heater game using CPUs, using existing code, and achieving even larger absurd run time estimates. And allows specifying start and end k values, so each of the many classes could be subdivided for greater futile parallelism.
Yeah, you are 100% correct.

Instead we should be TFing RSA-1024 (and ECMing also). It's smaller so it should be really easy.

I think you missed the trailing razz emoji in your quote. I put another one in here, I hope you don't miss that one also.
retina is online now   Reply With Quote
Old 2023-01-02, 21:52   #108
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

1,327 Posts
Default

A sincere question would be: How much ECM needs to be done on M1277 right now to reach the ECM target? This is a question that is likely only answerable if e.g. Ryan Propper and Sam Wagstaff state on how much ECM they have spent.

Last fiddled with by kruoli on 2023-01-02 at 21:58 Reason: Grammar.
kruoli is offline   Reply With Quote
Old 2023-01-02, 21:58   #109
Mark Rose
 
Mark Rose's Avatar
 
"/X\(‘-‘)/X\"
Jan 2013

2·1,549 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Note that Ken's citation of 660 core-years was an estimate for the matrix step. That step is usually 1/6 or so of the time spent sieving, so the whole job might be expected to take 7 times as long as the numbers Ken just mentioned.

Greg's development of GPU-enhanced msieve matrix solving has dramatically reduced the time required for the matrix solving step. If we sieved this job enough to get a matrix that would fit onto 8x A100 GPUs, a single system could solve the matrix in something on the order of a week. These numbers are based on scaling up from the GNFS-221 matrix job just completed (see Cunningham subforum), which was 114M matrix size, fit on 4x A100, and took 38 hours to solve on 8x A100. If we double the matrix size it would fit onto 8x A100 and take 4-5 times as long to solve.

So, on the order of 20,000 weeks on a single 12-core machine to sieve, and one week on a really fancy 8-GPU machine for the matrix.
168 hours of p4d.24xlarge at AWS is $5506 on demand or about $1600 using current spot prices.

The ~4000 core‐years is a little harder to come up with.
Mark Rose is online now   Reply With Quote
Old 2023-01-08, 16:07   #110
Andrew Usher
 
Dec 2022

2·3·37 Posts
Default

The difficulty then would be of the same order as the record factorisation of RSA-250, now 3 years ago. I would put this number to be somewhat a bigger deal than that. As for the ECM, even our limited Primenet records have it near t70, and I wouldn't doubt the real figure to be near t75 - surely this has been a very highly investigated number, perhaps the highest ever in ECM effort.

The job will be done by SNFS - either sooner or later - with very good odds. I imagine we'd prefer it sooner, but it's purely a matter of assembling the needed resources.
Andrew Usher 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 03:30.


Sat Feb 4 03:30:23 UTC 2023 up 170 days, 58 mins, 1 user, load averages: 1.05, 0.92, 0.88

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔