SoylentNews is people
SoylentNews
from the how-many-watts-were-needed-to-compute-the-result? dept.
A cryptographic puzzle proposed two decades ago that involves roughly 80 trillion squarings has been cracked much earlier than expected – in just three and a half years.
We say cryptographic because it involves a verifiable delay function [PDF], a moderately hard cryptographic function.
The conundrum was set by Ronald Rivest in 1999, the R in RSA and a computer science professor at MIT's Computer Science and Artificial Intelligence Laboratory (MIT CSAIL). Here's how he described the problem:
To solve the puzzle, first compute w = 2^(2^t) (mod n). Then exclusive-or the result with z. (Right-justify the two strings first.) The result is the secret message (8 bits per character), including information that will allow you to factor n. (The extra information is a seed value b, such that 5^b (mod 2^1024) is just below a prime factor of n.)
And t, n, and z are given, and are very large numbers: t is 79685186856218, and the other two have 616 digits each.
In announcing his challenge, Rivest promised to reveal the contents of a time capsule around 2033 – some 70 years after the opening of MIT’s Artificial Intelligence Laboratory, which has been revamped to MIT CSAIL, or when the puzzle has been solved, whichever is sooner.
[...] On Monday, the puzzle was solved by Bernard Fabrot, a self-taught independent Java developer from Belgium. The time capsule will, thus, be cracked open by Rivest for the world to see on May 15, and the secret message revealed.
The puzzle involves computing 22t (mod n), where n is a 2048-bit product of two prime numbers. You can try to solve the equation directly, but that would take too long. The mathematical enigma is also designed in a way that prevents the use of parallel computing to brute force the solution, since it’s impossible to compute it quickly without knowing the factorization of n. And it's a given you can't factorize n.
Instead, you can use successive squarings modulo n, starting with the number two. In other words, set W(0) = 2 W(i+1) = (W(i)2) (mod n) for i>0, and compute W(t), where t is the above big number. Here's an example of the calculation, using much smaller numbers for demonstration purposes: n is 253 (11 * 23) and t is 10. Then we can compute:
2(21) = 22 = 4 (mod 253)
2(22) = 42 = 16 (mod 253)
2(23) = 162 = 3 (mod 253)
2(24) = 32 = 9 (mod 253)
2(25) = 92 = 81 (mod 253)
2(26) = 812 = 236 (mod 253)
2(27) = 2362 = 36 (mod 253)
2(28) = 362 = 31 (mod 253)
2(29) = 312 = 202 (mod 253)
w = 2(2t) = 2(210) = 2022 = 71 (mod 253)
So, there you have it, 71 is the magic factorisation for the problem when n is 253 and t is 10. Now repeat this exercise with the actual numbers. Rivest predicted that the problem would be solved by 2034 judging by the amount of hefty compute required and the effect of Moore’s Law.
“The value of t was chosen to take into consideration the growth in computational power due to Moore's Law,” he wrote Rivest in setting the challenge.
[...] He believed that a single computer would have to be running for 35 years continuously, where the hardware would have to be upgraded every year to the next fastest chip available. But he underestimated the progression of hardware, as the problem has been solved earlier than expected.
Fabrot wrote the equation in a few lines of C code and called upon the GNU Multiple Precision Arithmetic Library, a free mathematical software library to run the computation over 79 trillion times. He used a bog standard PC with an Intel Core i7-6700 processor, and took about three and a half years to finally complete over 79 trillion calculations.
(Score: 3, Informative) by Snotnose on Tuesday April 30 2019, @01:33PM (10 children)
I've never seen a Windows machine run more than a few months without a reboot.
When the dust settled America realized it was saved by a porn star.
(Score: 5, Insightful) by Nerdfest on Tuesday April 30 2019, @01:43PM
Since he was smart enough to use the GNU Multiple Precision Arithmetic Library, I'd assume he's smart enough to use Linux or BSD.
(Score: 1) by evk on Tuesday April 30 2019, @02:23PM (7 children)
I've had my work machines go for 6+ months several times. 3-4 months would be normal between reboots.
I can't see why there would be a problem to run a Windows machine for 3.5 years if it's only using a small piece of dedicated software, the power stays up and you don't care about updates.
(Score: 2) by Freeman on Tuesday April 30 2019, @02:42PM (6 children)
#1 Updates are now forced.
#2 It's windows. You're not going to have a stable experience over 3.5 years.
Joshua 1:9 "Be strong and of a good courage; be not afraid, neither be thou dismayed: for the Lord thy God is with thee"
(Score: 4, Insightful) by mhajicek on Tuesday April 30 2019, @02:50PM (3 children)
Updates are not forced if you keep it offline.
The spacelike surfaces of time foliations can have a cusp at the surface of discontinuity. - P. Hajicek
(Score: 2) by Runaway1956 on Tuesday April 30 2019, @04:09PM (1 child)
They're working on an algorithm for that.
(Score: 0) by Anonymous Coward on Tuesday April 30 2019, @06:55PM
Network connections using power outlets should solve this. Hopefully his battery backup will support
assimilationtelemetry forwarding.(Score: 2, Interesting) by Anonymous Coward on Tuesday April 30 2019, @04:35PM
No need to leave off line. Mine has been on line for years and still does not have the updates. Turn on METERED SERVICE for connection. MS was yelled at for consuming bandwidth and costing people real MONEY and/or takes all the DSL pipe of a country in Africa.
Plus you can take out all of M$ scheduled tasks that try to force you to update.
(Score: 2) by ElizabethGreene on Tuesday April 30 2019, @04:38PM
See also: WSUS
(Score: 1) by evk on Thursday May 02 2019, @07:34AM
#1
I'm still on 8.1. Might be forced in 10. I don't know.
#2
I can't see why the last three years would be less stable than the first half year.
I've been doing daily work in Windows since NT4. The recuring crashes I've experienced during some periods have always been related to crappy third part drivers. There's lots of things I dislike with Windows, but saying that it's unstable is simply not true.
(Score: 2, Touché) by RandomFactor on Tuesday April 30 2019, @11:11PM
49.7 days was actually the maximum, but I'm dating myself.
Not that anyone sane ever considered trying to leave it running that long anyway back then.
В «Правде» нет известий, в «Известиях» нет правды