mersenneforum.org 20-year-old MIT LCS35 Time Capsule Crypto-Puzzle solved
 Register FAQ Search Today's Posts Mark Forums Read

 2019-06-14, 20:38 #45 Sergio Siller   Jun 2019 112 Posts Bernard Fabrot: Solves LCS35. Good job!
2019-06-14, 21:32   #46
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

3×2,239 Posts

Quote:
 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.

2019-06-17, 13:34   #47
TacticalCoder

May 2019

13 Posts

Quote:
 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.

 2019-06-17, 14:13 #48 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 3×2,239 Posts 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.
 2019-06-22, 07:33 #49 Sergio Siller   Jun 2019 310 Posts Solution !!! Congratulations CSAIL !!! Last fiddled with by Sergio Siller on 2019-06-22 at 07:41
2019-06-24, 02:38   #50
kevinhake

"Kevin W. Hake"
May 2019

5 Posts

Quote:
 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.

Last fiddled with by kevinhake on 2019-06-24 at 02:41

2019-06-24, 07:05   #51
Sergio Siller

Jun 2019

3 Posts

Quote:
 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!

2023-03-17, 07:25   #52
bur

Aug 2020
79*6581e-4;3*2539e-3

2CE16 Posts

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

Quote:
 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Tales From the Crypt(o) 52 2020-12-17 21:16 davieddy Lounge 4 2009-10-18 04:39 R.D. Silverman Lounge 2 2007-08-08 20:24 MrHappy Lounge 0 2005-01-19 16:27 E_tron Lounge 7 2004-06-29 10:17

All times are UTC. The time now is 15:45.

Sun Mar 26 15:45:21 UTC 2023 up 220 days, 13:13, 1 user, load averages: 1.43, 1.23, 1.07