20190525, 11:01  #34  
May 2019
13 Posts 
Quote:
I'm a bit of a hurry and my situation is "complicated" as I put my core i76700 in the time capsule at the MIT and now it's pure hell to find a sixth gen CPU where I live (plus credit cards issues, whatever)... Whatever, I'll come back later but here are a few notes ^ ^ The GMP authors kindly tried GMP from 1999 on 1999 hardware for me: they got basically 3800 sq/s. The original estimate was made by someone from RSA (not Rivest) and he got 3400 sq/s estimate (as compared to the 3800 sq/s the GMP maintainers just got on 1999 hardware running 1999 GMP). So the original estimate was super close to the actual value back then. However latest GMP version, on the same 1999 hardware, is basically 3.4x faster. So software alone there's more than a 3x speedup already. And at point GMP stopped being optimized for 32 bit architectures: GMP are sure another 25% speedup could be had. Switch from 32 to 64 bit then brought a 4x speedup basically: it's not just "twice the bits", it's also less instructions needed. Some instructions are now taking less cycles per instruction: so speedup there too. Basically from my research original estimates were very close (and this has been tested)... But it's hard to predict the future, even for Ron Rivest ; ) If anyone wants to look at Ron talking then me (private link atm): https://www.youtube.com/watch?v=hmwT...ature=youtu.be The ceremony with the capsule being opened / resealed (4 minutes vids): https://www.youtube.com/watch?v=9qKk...ature=youtu.be Talk to you all later, 

20190525, 14:48  #35  
"Marv"
May 2009
near the Tannhäuser Gate
3·269 Posts 
Quote:
https://www.mersenneforum.org/showthread.php?t=21634 I wonder if using the ASIC being discussed would be more feasible ( assuming it works ) ? 

20190525, 15:45  #36 
"Robert Gerbicz"
Oct 2005
Hungary
3·5·109 Posts 
The new puzzle from Ronald L. Rivest is out!!!!!
http://people.csail.mit.edu/rivest/p...newpuzzle.txt Now n has 3072 bits, t=2^56, with milestone puzzles, you have 15 years to match the original year 2034. 
20190525, 16:58  #37 
May 2019
D_{16} Posts 
If I'm not mistaken this is the error check Shamir suggested to Rivest for the LCS35 puzzle and that error check is explained in the original puzzle description : )

20190525, 16:59  #38  
May 2019
13 Posts 
Quote:


20190525, 17:08  #39  
May 2019
13_{10} Posts 
Quote:
Also MPIR is a fork of GMP right? So maybe I tried on an old GMP version which for whatever reason did behave that way. 

20190525, 20:28  #40 
"Robert Gerbicz"
Oct 2005
Hungary
3·5·109 Posts 
For the original puzzle the seed value for p was in the message, but easily we can get the very likely original seed value for (the other prime) q.
Code:
? nextprime(lift(Mod(5,2^1024)^67229033994487263541238668735266739881324356552223677298756897562133)) %1 = 40853923313791905056390006230327028982596606945346318846549337657379367189284051739393623398120773967666443351405399733470781263258210328375697986182263865342952431430451931199880262185216184022204644820522254304557640038220504811993426511340296997627585129527426806995411578324937406976125239089383993333731 
20190525, 23:08  #41  
May 2019
13 Posts 
Quote:
Sounds an order of magnitude too low for GMP though! 22 minutes to do 1 billion operation using GMP on my core (ex) i76700 from 2015. "ex" because now my core i76700 ain't mine anymore: he's inside the time capsule and belongs to the MIT : ) I was saving a file every 1 billion iteration to disk. And that's not the most optimized way to do it. I was doing about 750 000 steps per second. While preparing my slides and reading some of the suggestions here by Gerbicz I could reach about 880 000 steps per second IIRC. Someone with a core i9 told me he had 990 000 steps per second (probably that a bit more is doable). 

20190526, 03:39  #42 
May 2019
3·37 Posts 
You are right. Thanks for pointing that out. If I have not mistaken, the Gerbicz error check applies and it is much stronger than the error check Shamir suggested back in 1999.

20190526, 23:55  #43  
"Kevin W. Hake"
May 2019
5 Posts 
Quote:
When I implemented the square + mod it was slower until I used the lower level interface to reuse buffers between the two. But yeah I should try it in the latest GMP and see. 

20190603, 00:07  #44 
May 2019
13 Posts 
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). Once the main computation has computed up to, say, 32 billion (I'm just making up an example using multiple of 1 bn and 32 cores), you can start 32 computation on 32 cores on other machine(s), using whatever method you want, and have each core start at a different intermediate result (taken from the main computation). So you're effectively computing in parallel. This works as long as your have a main computation giving you intermediate results. Which means there's no need to implement any verification check at all in the "main" computation. And the cost of the verification is not very important: you can parallelize the second computation to as many cores as you want (so using say the verification Shamir suggested in the original LCS35 puzzle with a bigger prime ain't a problem). The cryptophage team did something similar but, as far as I know, they didn't implement any verification at all: they just ran the same computation parallelized, on regular PCs (while the main one was running on a FPGA). But they could just as easily have added a check to the second computation. This keeps the FPGA / ASIC implementation simple (and faster). But then it's late and I may be way off! Last fiddled with by TacticalCoder on 20190603 at 00:16 Reason: grammar 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Crypto News  Nick  Tales From the Crypt(o)  52  20201217 21:16 
I hate this time of year  davieddy  Lounge  4  20091018 04:39 
Crypto 2007  R.D. Silverman  Lounge  2  20070808 20:24 
crypto game  MrHappy  Lounge  0  20050119 16:27 
Is it time to change the CPU year measurement?  E_tron  Lounge  7  20040629 10:17 