20-year-old MIT LCS35 Time Capsule Crypto-Puzzle solved

[Sergio Siller]

Bernard Fabrot: Solves LCS35. Good job!

[retina]

Originally Posted by TacticalCoder

Just quoting a random message talking about verification perfs...


For this kind of problem (LCS35 / CSAIL19) the speed of the verification method has not much importance if I'm not mistaken because you can always, as the second team did (the ones using a FPGA) parallelize as many verification as you want as soon as you have the "main" computation starting to give up intermediate results. For the main computation you want to be as fast as possible: so no verification at all (this also simplifies, for example, FPGA code/setup).

You can also just duplicate the FPGA setup and run two or more in parallel. If cost isn't a factor then this is probably the most straightforward approach.

The result won't come any faster, but you can detect an error sooner and backtrack with the loss of only one iteration.

[TacticalCoder]

Originally Posted by retina

The result won't come any faster, but you can detect an error sooner and backtrack with the loss of only one iteration.

If wonder if the best approach (if the goal is to solve it as fast as possible) is not to run one computation without the check (so working with 2048 bit numbers) and then having the second computation running with the check (say performing a 2096 bit multiplication).


I realized that in my case a slowdown on my main computation of 2% and I wouldn't have been the first to find the solution! And I did try: using a 50 bit prime for the check would slow my main computation of more than 5%.


So I wouldn't have win had my main computation been running the check.


Now of course if the second computation runs with the check and an error is detected near the beginning, you don't lose much time to backtrack from the last correct intermediate result.


But if the second computation detects an error towards the end, because the second computation is x% slower, it means the main computation needs to backtrack by x%, which can be quite some time.

[retina]

I think just running two instances of the same capability in parallel is very easy. So they can run in lock step with each other. Instant verification after each iteration with a comparison circuit that can signal a backtrack if there is a difference.

[Sergio Siller]

!!! Congratulations CSAIL !!!

[kevinhake]

Originally Posted by TacticalCoder

But if the second computation detects an error towards the end, because the second computation is x% slower, it means the main computation needs to backtrack by x%, which can be quite some time.

The second computation can be multi-threaded; every time your main, fast computation records its progress, a thread can be spun up to check it. So let's say your main thread records progress every 5 minutes. Even if the secondary check ran 50% slower, 2 cores would complete 2 of those blocks in 10 minutes (or 1 block in 5 minutes, the same rate as the main thread); they would never fall far behind.

[Sergio Siller]

Originally Posted by Sergio Siller

!!! Congratulations CSAIL !!!

Mersenne Forum did not let me edit the post.
jk, but I will build a machine to attempt and crack this problem.
Have an excellent day everyone!

[bur]

Unearthing this thread.

Obtaining the solution yields a clue on how to factor n:

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^1536) is just below a prime factor of n.)

Why this peculiar construct? Is it to conserve space while not giving any useful information about the factor?