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 ;)