EDIT: WIRED article just in. Haven't read it yet. Link if anyone is interested: https://www.wired.com/story/a-programmer-solved-a-20-year-ol...
EDIT2: forgot to tell but the mining pool Antpool posted a message in the block header / coinbase data of Bitcoin's block 573138 saying "Congrats Bernard Fabrot for solving LCS35!". My brother tried to time this with the press release which was supposed to come out on friday but then the press release got pushed back to today/monday. So yeah, coinbase data of block 573 138 is kinda very cool (it requires cooperation of a mining pool because it's not just in a transaction but in a block). TYVM to the everybody at Antpool! Big thanks for that : )
It seems as if your 2014 comment hinted at this project. Applause for keeping this tight lipped for those years.
>Java is quite fast compared to most languages but for some things it is still terribly slow compared to C / C++. I had to do some big integers crunching lately and tried: Java, Go, Go with GMP, C (GMP) and Haskell (using GMP under the hood). Eventually I went for good old C with the latest GMP version for it was the fastest for my use case (with Haskell and Go with GMP coming close but still not as fast as C).
Java was, for the computation I needed to do... Eight times slower than C! I know I was hitting a edge case for a very specific kind of computation but still. 
As an aside, .NET Core 3.0 will deliver access to intrinsics - not sure if Java or any other managed platform already has this?
Yeah I'm sorry that my comment from late 2014 gave that false impression that I said GMP was written in C. What I meant was that it was, when I did the testing, slightly faster to call GMP from C than from Haskell, Clojure, Java. I remember I tried all these back then and calling GMP for C was a bit more efficient. Now I know there are now ways to call libs like this from Java without paying the old foreign function call penalty: but I didn't know about that in 2014. So I called GMP from C because it was faster. Out of memory I'd have said GMP was C with inline assembly but I may be wrong ; )
Rich Tea is a British biscuit. Maybe that's why you remember it?
TacticalCoder last HN comment is from Dec 5, 2015. Checks out.
Kudos to you, well done!
Pretty sure @dang would have accepted that!
Was this a side project? did it require much attention after the initial setup?
Totally a side project.
It hardly required any attention: just making sure the computation was running and making sure to backup the intermediate results once in a while (I had backups everywhere of the intermediate results: remote servers, USB keys, DVD, other computers at home, email, etc.).
I only needed to do a few tiny steps once I found the secret message (which contains a number which allows to compute one of the two prime numbers).
The description of the problem itself explains a way to verify that intermediate results are correct.
> Did you have an estimation of the date?
Yes and that one is easy: I wrote a little piece of code (in Clojure, whatever, it's unrelated to finding the solution) which would check at which intermediate result the computation was and then compute an "ETA".
Fun story: I'd regularly send my brother something like this...
:eta "1 year 2 month(s) 26 day(s)"
(that's an actual estimate I found in my old emails)
I didn't realize... Your comment is actually extremely funny: I love it : )
Yeah, it's more or less when I started computing that. This is hilarious.
I'd love to hear more about it: you can email me bernard @ fabrot dot com
> "We estimate that the puzzle will require 35 years of continuous
computation to solve, with the computer being replaced every year by
the next fastest model available. Most of the work will really be
done in the last few years, however."
So how were you able to perform a calculation that should take 35 years in just 4? Where did Rivest get his assumptions wrong?
SIMD instructions lowered the amount of cpu cycles needed per operation.
Novel algorithms lowered the amount of operations needed per iteration.
 https://people.csail.mit.edu/rivest/lcs35-puzzle-description... (short description at the bottom).
The problem is designed so that iterations have to be sequential, but a single iteration can use parallelism.
So mine isn't a cryptographic question, but I'd love to know what steps you took to ensure integrity and uptime of your consumer i7 hardware, and capture of each partial step of the solution, while you ran your algorithm.
EDIT: also, congratulations! (How did I leave that out!?)
I basically used my everyday workstation. There were 79 trillions operations to be made and I'd save the intermediate result every 1 billion result (so approximately every 22 minutes I'd save a result).
The computation cannot be parallelized and the i7 I was using has four cores. So basically instead of turning it every night off I'd simply leave it running 24/7.
I'd simply backup the files with the intermediate results once in a while. I rebooted the computer about 50 times in 4 years and during those 4 years during about 3 and half years it was computing towards the solution.
But I coded (totally unrelated things), compiled things from source, browsed the web, did my email, etc. from the very workstation which computed the solution.
The computation is easy to relaunch from any intermediate step.
Thanks for the congrats!
This reminds me of a time during college a professor gave us an extra credit assignment to essentially find prime factoring large numbers (classic problem). I had come up with a pretty bad solution, but thought it might just finish in time for the deal line if I left it running all week. Of course a transformer blew up the day before the deadline, and I never knew... chances are my program would have never terminated :P
Basically I like my workstation to be quiet. Really very quiet: as in I can only hear it if I put my ear on the tower. So I never have ultra power hungry CPUs. I don't game so no GPU besides the integrated one. A M.2 SSD which consumes next to nothing.
Power bill probably did increase a bit but honestly it was lost in the noise: I definitely didn't notice anything : )
Is there a proof of this somewhere? Operations that seem vaguely similar, like doubling repeatedly, can be easy to "parallelize".
Each step depends on the result of the previous step. I don't know of any claim that the crypto/maths behind the paper do not hold.
You can use a FPGA or build an ASIC: but as far as I know as long as the crypo in this paper hold, it's not parallelizable.
But this doesn't mean anything. If I said to take a number and add 1 eighty trillion times, each step would depend on the result of the previous step, but obviously it would be unnecessary to actually compute each step.
A fast way to calculate something like `g^x` for some large `x` is to iteratively square:
Of course, this doesn't prove that computing `g^x` is sequential, but it does show why it is different than computing `1+1+...+1`.
You can compute g^(2^i) by just multiplying g's in the same way that you can compute 2^i by adding 1s, and multiplication is as associative as addition is. Specifying that you want g^(2^i) rather than g^k for some arbitrary k looks like a way of ensuring that a partial product computed in parallel (say, g^3) will be of nearly no value, because every partial product that helps compute the total will already be produced by the single agent doing squares.
So why compute g^(2^i) rather than just 2^i? Is 2^i in fact hard to compute? (In binary representation, it certainly isn't, but maybe 3^i is?)
OK, I read the paper.
This is the entire discussion of the inherent difficulty of repeated squaring:
> More importantly, repeated squaring seems to be an "intrinsically sequential" process. We know of no obvious way to parallelize it to any large degree. (A small amount of parallelization may be possible within each squaring.) Having many computers is no better than having one. (But having one fast computer is better than one slow one.) The degree of variation in how long it might take to solve the puzzle depends on the variation in the speed of single computers, and not on one's total budget.
I see two problems here:
(1) This is a purely conclusory argument, suggesting that a better response would have been a simple "no, there's no proof".
(2) This does not even attempt to address the question I posed, which was whether it is necessary to compute the intermediate results in order to compute the final result.
In fact, we know that the intermediate results are not necessary to compute the final result, because that is how the message gets enciphered in the first place. It can be done by factoring the modulus, and obviously there is no proof that that is difficult to do.
But beyond that, it also isn't immediately obvious that it must necessarily be impossible to compute the final result directly by means that don't require factoring the modulus. It is possible that somewhere in the literature on Blum Blum Shub this question has been analyzed, but that goes a bit beyond your suggestion to "read the paper".
So, I'm stumped. Tell me what you saw in the paper that you thought would answer my question?
Well, there's no mathematical proof. But physicists and judges would accept that there's lots of money and fame to be made breaking eg RSA, so countless people have tried and keep trying, but haven't come up with much good so far.
This is similar to the answer to, "Is there any proof that RSA is uncrackable?"
The security is based upon the assumed hardness of certain mathematical problems.
OS is Debian stretch: it's rock solid in my experience.
It was rebooted on average once a month (I switched country, there were black outs, I upgraded the OS, etc.) but there have been stretches where it was up for several months in a row, happily cranking!
From Rivest-Shamir-Wagner's paper:
“Solving the puzzle should be like having a baby: two women can’t have a baby in 4.5 months."
first thanks a lot for posting this to HN!
Then: is there a question somewhere in your post which I missed? : )
How did you beat Peffers' team? Did you simply start the computation sooner, or did you reach some insight that eluded them?
"In mid-March, the group began to run an algorithm" ... "FPGA was about 10 times faster than a high-end commercial CPU running non-optimized software. Based on the chip’s computing efficiency" they "calculated that they would have the correct solution" "on the evening of May 10, just two months after they started the calculation. Yet when they reached out to MIT to let them know a solution was imminent, Rivest informed them that Fabrot had beaten them to the punch."
We read here that he started end of 2015! Rivest believed at the time he constructed the puzzle, almost 20 years ago, that he has constructed the puzzle that would keep the vault locked until 2034, based on his expectations then of the increase of the computing speed. Obviously, predicting the developments of 35 years is not so easy, and the single-CPU computer speeds did improve faster. Anyway...
I’d really like to know about those! Any links?
No disrespect intended to that team. It's an impressive accomplishment, and they're the ones who can publish in a journal for all due academic credit.
However, it also depends on what you value. Sometimes for some problems crossing the finish line first is winning, or seems able to simply allow the worlds technical advances to compound faster than more novel approaches whose future utility is unknown.
During all those years one person stopped to think about the goal in the most optimal way and ask, what's really the simplest solution here? Is custom hardware the only practical way? Everyone was allowed to think about implementation costs.
In other words, the most impressive part is what was not done. Great work.
Yeah, always nice to see who you can run into on hackernews! I'm sure there's plently of us Belgians lurking on here :)
Are you by any chance planning to release your source after the ceremony? It'd be really interesting to read some peak-efficiency GMP code as that's a library I've always been interested in.
Additionally, do you happen to know how much longer it could take to factor modulus n and then compute the value for 2^(2^t) using the methods described in the paper? i.e. instead of repeated squaring compute
2^(2^t mod phi(n)) mod n
AMD Phenom(tm) II X4 B50 Processor
56.674783% (0x2912f5a00000 / 0x48792741a51a) ETA: 1 year 138 days (2020-09-18)
Already answered somewhere but lost in this thread...
Hardly anything. Relaunching the computation after a black out or an OS reinstall or when I moved from one country to another : )
Also once in a while going ballistic with backups as to not lose x months / years of computations.
Then at the end doing as the puzzle says to do: xor to get the secret message. Get b from the secret message and do 5^b mod (2^1024) then find the first prime above the resulting number. Divide n by that first prime to get the second prime. This took no time.
> What do you think you do in your life that might have given you a leg up in cracking the puzzle ?
I don't know. It required finding it (mostly chance there), reading it and understanding how the parameters were set up, realizing that a solution could probably be found in some "reasonable" amount of time and then it required some dedication (and maybe a tiny of crazyness too) to run if for so long.
I clearly always liked optimization and learning new languages and trying libraries and whatnots: so as the solver was simple to implement I was easy to quickly try different languages / libraries. I kinda knew upon reading the puzzle that there was a good chance that it could be solved faster than expected.
But really it's like 10 or 12 lines of code. I spent some time doing performance tests but besides that it was just being patient?
I was clearly motivated by the idea that I could be the first one to find the solution to this puzzle. That one carrot worked wonderfully on me : )
Great job. Kudos.
EDIT: got it, it's LG 38UC99-W.. thanks
As the problem states: there's a number allowing to factorize n. There's also a little message.
I haven't done many from Project Euler but I did participate a lot in the "TopCoder" competition back when TopCoder started (that'd be many many years ago).
I think it's a great way to learn about algorithms or to learn a new programming language.
Is the answer.... 42? :)
In all seriousness, I hope that on May 16th you will post your efforts/solutions/other miscellanea somewhere, and will come back to HN and make a "Show" post for us all to admire and celebrate with you.
I don't have a blog (yet) but I do have a few things I'd like to write about (not just this puzzle) and share with other enthusiasts so I think I'll simply start a blog. But it won't be on the 16th: I'll need some time to come back home etc.
As dsincl12 wrote it's indeed a 38": the LG 38UC99-W.
And you're correct, good catch: it's the Awesome WM running on Linux (Debian Stretch). For the geeky details: it's Awesome WM but with a patch I modified doing "useless but not useless" gaps. Basically it adds gaps between the top bar and between the windows, but it doesn't add gaps on the edge of the screen (which to me makes the more sense but YMMV).
So yeah a Core-i7 6700 / 16 GB of RAM / NVMe M.2 PCI-e 3.0 x4 SSD, which is my daily workstation (as I wrote elsewhere in this thread: I solved this on my everyday workstation).
I've got 12 virtual workspaces set up and my "main" one is in a three columns layout (with Emacs in the middle ;)
I have a question and maybe someone can answer it: This indicates that knowledge of the factorization of the modulus n allows to do this calculation faster, which is likely how the designers of this puzzle calculated the result.
However it's not explained how that happens and how the factors of n help. I assume this may be someone related to RSA, as there you also are able to do something much faster if you know the factors of a combined modulus. However in RSA you're able to invert a modular exponentiation. Here you seem to be able to speedup many successive exponentiations.
Is there some clever way to translate these two problems into each other and thus use an RSA-like method?
(Update: I found this paper https://people.csail.mit.edu/rivest/pubs/RSW96.pdf which explains how to do the calculation on page 4, but is still lacking an explanation why. But I guess for people fluent in number theory it's probably somehow obvious.)
It's "obvious" to the people who are aware of how RSA works, and know that Rivest based his derivation of the puzzle on the properties on which RSA encryption also depends.
Note, Rivest is one of Rivest–Shamir–Adleman: "The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978."
In shortest and simplest, the "hardest" part is just that the numbers which have to be processed are huge and that nobody knows an algorithm which would avoid doing a lot of the calculations to factor such huge numbers. Then for Rivest as he created the "puzzle" the goal was just how to construct one special huge number which encrypts the message. Constructing all that is then by a clever design faster than solving. Those who try to solve the puzzle don't have the exact construction numbers Rives used, just the result which has to be attacked by "brute force" calculations. The intermediate results during that process aren't predictable faster than simply calculating them, but every next depends on the previous one.
But not everything related to RSA is mathematically rigorously proved, as you can see in the Wikipedia article.
We want to find the value of 2^(2^t) mod n where n = pq. It's a well known number-theoretic fact that 2^phi(n) mod n = 1, where phi is the Euler totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function).
This theorem is called Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_theorem). For n = pq, phi(n) = (p-1)(q-1)
So if 2^phi(n) = 1, then 2^(2 * phi(n)) = 1 and 2^(3 * phi(n)) = 1 and so on, so we really only need to know the value of 2^t mod phi(n). We can compute this value in O(log(t)) operations via repeated squaring, and once we know this value (let's call it k), then we just need to compute 2^k mod n to finish, which again, can be done quickly using repeated squaring.
Here's a quick demo in python:
>>> p = 8721676787107355947610787701585837629266743108012786178142468507932506290346645194233003705268505408163930982434418938387386290453411395078603729114734341
>>> q = 8903989072246145056499086678843460912573461209473391355874543630090691433843393509873230695095738299681258115825746186699033768361727241007153178256782969
>>> n = p * q
>>> phi = (p - 1)*(q - 1)
>>> t = 1000
>>> x = 2
>>> for _ in range(t):
... x = (x*x) % n
>>> k = pow(2, t, phi)
>>> y = pow(2, k, n)
>>> x == y
Good you post this because I had no idea what I could keep my computer busy with now that LCS35 is solved ; )
Is that not epic? : )
Now I think it's fair to say that part of the solution also consisted in realizing that using a fast big integer library it was doable in three years something.
Does that mean that you could, if you wished, have switched to a different machine and just continued where you left off? E.g., could the Peffers team, if they knew about it, theoretically have taken your partial results and run them on their FPGA to obtain the final result a little bit faster than if would have been otherwise?
(Not suggesting this is in any way what you should have done. Just curious)
Totally. It's even explained in the original problem description: the idea was that every year you'd switch to more efficient hardware, picking up the computation where you let it off, until Moore's law stopped applying.
I considered upgrading from my i7 6700 to a 8700-K overclocked for slightly faster clock speed (and maybe some instructions taking fewer cycles). It'd have saved some time.
... but then I realized that N is a product of two primes, which Rivest knows, so he can take a shortcut and compute the answer faster. That is, the answer is known.
But this makes you wonder if factoring that N would've been a faster route to solving this puzzle. What do you guys think?
Can you tell us a bit more about your self-taught background? What do you do for a living? How did you hear about the challenge?
> Can you tell us a bit more about your self-taught background?
Sure... I started programming in BASIC at 11 years old on the most inconceivable setup ever: an Atari 2600, which was a gaming console (the infamous one which lead to the video industry crash of 1983 with a landfill filled with E.T. cartdridges). So how do you write BASIC on that at 11 years old? Well your mom offers you a "BASIC cartridge" which comes with a keyboard in two parts you plug in the joystick ports! (horrible experience but I do remember writing tiny programs drawing colored lines using that).
Then the Commodore C-64: more BASIC, some assembly using a "power cartrigde", mainly to modify (hack?) games. Then the Commodore Amiga: learning to write intros and demos. Then the PC (386, 486, and so on): writing a video game (finished but never published but it landed me my first job: long way too long story), writing more intros and demos (won a PC demo compo in Sweden). I'll blog one day (when I'll have a blog) about that PC / DOS video game which was running at 60 Hz on a 386 because it used a cool collision detection method I came up with (which as far as I know is unique and was pixel perfect even back then and was and still is particularly efficient). I still do have both the source and the binary for that game.
For the languages I mainly did BASIC then assembly (680x0 and 80x86), C with inline assembly, C++, Java... Then I stuck with Java for a very long time. Got a Sun Certified Java Programmer certification around 2000 (which makes me an oldtimer): only cert I ever got.
I cannot say I didn't do boring Java consultancy for even more boring companies/organizations. And thankfully once in a while a fun professional project ; )
Nowadays I'm still programming in Java as for my own projects I like to write proof of concepts using Clojure (and ClojureScript). And as I'm an Emacs (IntelliJ for Java though) user if of course waste a lot of time with elisp, hacking my Emacs config!
I hope you still love HN ; )
If you're a hardware engineer (or mathematician) interested is building an ultra-low latency ASIC, please email firstname.lastname@example.org
So how did Rivest create the puzzle back then in the first place, without taking 35 years to generate it?
1. multiplying two large prime numbers together (easy)
2. Factoring the result without knowledge of those primes (extremely difficult)
3. Factoring the result with knowledge of one of the primes (easy)
For this puzzle, knowing the factorisation of n allowed a shortcut to quickly generate the puzzle, but without that factorisation it required squaring numbers 79,685,186,856,218 times sequentially so parallelism isn't a help.
The actual code to generate the puzzle was in the original puzzle description at https://people.csail.mit.edu/rivest/lcs35-puzzle-description... .
It's very inspiring to see a self-taught programmer achieve such an impressive result.
Any chance of the capsule ceremony being live streamed? Would be cool to follow.
Keyboard is a Happy Hacking Keyboard Pro JP. Mat was a gift from my brother and I have no idea where it comes from. Monitor is a LG. Watch is a slightly fancy swiss mechanical diver's watch ; )
One questions: Solving this puzzle has any impact on Verifiable Delay Functions security (specially Chia's VDF)?
>> Cryptophage project solved it in 2 months.
What about ASICs (NSA's power and love!)? How long would it take? any estimation? 2 days? :-)
Thanks and congrats to you as well for reducing the calculation time!