This MIT puzzle was believed to be unsolvable for 35 years. Here’s how Bernard Fabrot cracked it 15 years early.

"It's really very simple."

Bernard Fabrot
Bernard Fabrot –Rachel Gordon / MIT CSAIL

In 1999, when longtime MIT professor Ron Rivest created a cryptographic puzzle to celebrate the 35th anniversary of the school’s Laboratory for Computer Science, he said it would be another 35 years before anyone could possibly solve it.

Rivest said the puzzle would take 35 years of continuous computing, along with switching out the computer performing it with the next fastest model each year. He said it would require a virtually unimaginable number of steps.

“Most of the work will really be done in the last few years, however,” Rivest said at the time.

What he didn’t expect was for all of the work to be finished in a few years — and a decade and a half ahead of schedule.

Advertisement

“I did for fun,” Bernard Fabrot, a Belgian freelance software developer, told Boston.com.

“It was long overdue that someone eventually came up with an answer,” he added.

Tell that to 1999’s Rivest.

MIT announced late last month that Fabrot, a self-taught programmer, solved the puzzle in three-and-a-half years by using his own everyday PC equipped with an Intel Core i7-6700 processor.

“I was just using a regular PC,” he said. “I mean, I’m a software developer, so I have a state-of-the-art PC, like, a very fast PC. But it’s still just a PC.”

As a result of the puzzle being finished 15 years early, school officials opened a 1999 time capsule that was filled with epochal tech artifacts, including the original 1992 proposal for the World Wide Web from Tim Berners-Lee, who is now an MIT professor, and Microsoft’s first-ever product, the Altair BASIC interpreter, donated by Bill Gates.

Fabrot, who is now lives in Spain, said he began programming when he was 11 years old.

“Like all the kids, you wanted to program games,” he said. “That’s what I wanted to do. That’s now 35 years ago. And it’s a lifelong passion and I never quit learning, and I always loved it.

Advertisement

Fabrot said he stumbled upon Rivest’s puzzle, the LCS35, online in late 2014, where it had been long bandied about on forums and social media — but never solved. Fabrot decided to take a try.

“It’s really very simple,” he said.

Designed to be “intrinsically sequential,” the puzzle couldn’t be solved using multiple computers. And while the equation — “compute 2^(2^t) (mod n) for specified values of t and n” — may seem straightforward, it involved calculating the square root of the starting number nearly 80 trillion times.

Yes, 80 trillion. Fabrot said the operation ends up working with huge numbers of up to 616 digits.

“It quickly gets out of hand,” he said.

The sheer volume of successive steps done by a single computer was the reason Rivest thought the problem would take so long. However, the MIT professor said he underestimated how fast computing technology would become.

“There have been hardware and software advances beyond what I predicted in 1999,” Rivest said in a statement after Fabrot cracked the puzzle, adding that “the resources required to do a single squaring have been reduced by much more” than he could have thought 20 years ago.

Coincidentally, a team of computer scientists that was also working on the puzzle finished it two weeks later than Fabrot. It took them just two months to crack.

“It was just that you had to do many, many, many steps, and I realized basically that the way computers evolved 15 years after the puzzle was created meant that it was possible to solve it on a regular PC much faster than what was expected in 1999,” Fabrot told Boston.com.

Advertisement

After some mental math, Fabrot realized the puzzle could be solvable in a few years by using the latest technology. So in mid 2015, he bought a new, faster central processing unit (CPU) and set up his PC to do the computing in the background while he did his everyday work. Fast forward to 2019, after trillions of squaring operations and a few additional equations, Fabrot completed the puzzle, which rewarded him with a short message.

“There was a little message saying ‘Happy birthday LCS,” Fabrot said, noting it was a tad out of date.

MIT’s Laboratory for Computer Science merged with the school’s Artificial Intelligence Laboratory in 2003 to form the Computer Science and Artificial Intelligence Laboratory, or CSAIL, which hosted last Wednesday’s time capsule reveal.

As part of the ceremony, Fabrot said MIT resealed the time capsule with both the original and some new artifacts, including the CPU he used to solve the puzzle. Rivest also created another problem to go along with it.

“I may take a look at the new puzzle,” Fabrot said.