mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Tales From the Crypt(o)

Reply
 
Thread Tools
Old 2019-06-14, 20:38   #45
Sergio Siller
 
Jun 2019

3 Posts
Default

Bernard Fabrot: Solves LCS35. Good job!
Sergio Siller is offline   Reply With Quote
Old 2019-06-14, 21:32   #46
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·1,571 Posts
Default

Quote:
Originally Posted by TacticalCoder View Post
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.
retina is offline   Reply With Quote
Old 2019-06-17, 13:34   #47
TacticalCoder
 
May 2019

11012 Posts
Default

Quote:
Originally Posted by retina View Post
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.
TacticalCoder is offline   Reply With Quote
Old 2019-06-17, 14:13   #48
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

188C16 Posts
Default

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.
retina is offline   Reply With Quote
Old 2019-06-22, 07:33   #49
Sergio Siller
 
Jun 2019

3 Posts
Default Solution

!!! Congratulations CSAIL !!!

Last fiddled with by Sergio Siller on 2019-06-22 at 07:41
Sergio Siller is offline   Reply With Quote
Old 2019-06-24, 02:38   #50
kevinhake
 
"Kevin W. Hake"
May 2019

5 Posts
Default

Quote:
Originally Posted by TacticalCoder View Post
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
kevinhake is offline   Reply With Quote
Old 2019-06-24, 07:05   #51
Sergio Siller
 
Jun 2019

3 Posts
Default

Quote:
Originally Posted by Sergio Siller View Post
!!! 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!
Sergio Siller is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Crypto News Nick Tales From the Crypt(o) 52 2020-12-17 21:16
I hate this time of year davieddy Lounge 4 2009-10-18 04:39
Crypto 2007 R.D. Silverman Lounge 2 2007-08-08 20:24
crypto game MrHappy Lounge 0 2005-01-19 16:27
Is it time to change the CPU year measurement? E_tron Lounge 7 2004-06-29 10:17

All times are UTC. The time now is 14:44.


Fri Oct 22 14:44:30 UTC 2021 up 91 days, 9:13, 1 user, load averages: 1.22, 1.15, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.