Self-taught programmer cracks puzzle by MIT researchers that was supposed to take 35 years to solve
Twenty years ago, MIT researchers revealed a puzzle that was supposed to take 35 years to solve.
But Bernard Fabrot, a self-taught programmer from Belgium, managed to pull off what once seemed impossible. This week, MIT officials announced that Fabrot found the solution to the cryptographic puzzle in less than four years — and 15 years earlier than they originally expected.
Fabrot spent the last three and a half years computing the solution, according to a story on MIT’s Computer Science and Artificial Intelligence Laboratory website.
MIT officials also noted that another team, led by Simon Peffers, a former engineer for Intel, is also close to cracking the puzzle and is expected to have the solution ready by May 11.
The crypto-puzzle, known as LCS35, was first announced in 1999 in conjunction with the 35th anniversary celebration of MIT’s Laboratory for Computer Science.
MIT officials said the puzzle involves doing about 80 trillion successive squarings of a starting number. When he first issued the puzzle challenge in 1999, MIT professor Ron Rivest expected that it would require “35 years of continuous computation to solve, with the computer being replaced every year by the next fastest model available.”
Of course, the puzzle ended up being solved sooner than that.
In an e-mail, Fabrot said Wednesday that there’s “been no mathematical breakthrough.”
Fabrot wrote that he “had my computer do the 79 trillions operations needed to solve the puzzle. I realized that by using a fast library for doing big integer multiplication I could find the answer in 3 years and half: so I knew that by 2019 I could have the answer . . . The code itself is simple but it required patience and perseverance.”
Rivest said in the news story posted to MIT’s website that there have been “hardware and software advances” beyond what he predicted in 1999.
“The puzzle’s fundamental challenge of doing roughly 80 trillion squarings remains unbroken, but the resources required to do a single squaring have been reduced by much more than I predicted,” Rivest said.
Back in 1999, MIT officials had promised that if someone came up with the correct solution before the year 2033, they’d open a time capsule that contains all sorts of tech treasures, including artifacts from World Wide Web inventor Tim Berners-Lee and Microsoft founder Bill Gates.
They are making good on that promise: MIT officials announced that the time capsule ceremony will be held May 15 at 4 p.m. at MIT’s Stata Center.
And Fabrot, who is currently living in Spain, plans to be there.