20190503, 17:10  #1 
"/X\(‘‘)/X\"
Jan 2013
https://pedan.tech/
2×3^{3}×59 Posts 
20yearold MIT LCS35 Time Capsule CryptoPuzzle solved
This week MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) announced that a 20yearold cryptographic puzzle was just solved by a selftaught programmer from Belgium, 15 years earlier than MIT scientists expected.
Bernard Fabrot spent the last three and a half years computing the solution to a puzzle first announced by MIT researchers in 1999. https://www.csail.mit.edu/news/progr...graphicpuzzle https://people.csail.mit.edu/rivest/...escription.txt 
20190503, 20:18  #2 
"Robert Gerbicz"
Oct 2005
Hungary
3·5·109 Posts 
"Bernard Fabrot spent the last three and a half years computing the solution to a puzzle first announced by MIT researchers in 1999.
.. The puzzle essentially involves doing roughly 80 trillion successive squarings of a starting number .. Fabrot used a simple Intel Core i76700 found in consumer PCs, and computed the solution using the GNU Multiple Precision Arithmetic Library (GMP)." I could get this in roughly 2.14 years on identical hardware, without going very deep we can use the faster mpz_powm with some intelligence, test: I can complete 40 million iterations in 34 seconds. Do the math. Code:
Read n=6314466083072888893799357126131292332363298818330841375588990772701957128924885547308446055753206513618346628848948088663500368480396588171361987660521897267810162280557475393838308261759713218926668611776954526391570120690939973680089721274464666423319187806830552067951253070082020241246233982410737753705127344494169501180975241890667963858754856319805507273709904397119733614666701543905360152543373982524579313575317653646331989064651402133985265800341991903982192844710212464887459388853582070318084289023209710907032396934919962778995323320184064522476463966355937367009369212758092086293198727008292431243681 has 2046 bits. ans=4994097331495993759590792520652782896298040702842052804596091316575363414862676472297324459047461969855851762208911221321241374084825500814598324057817295157460163428748617431743371535373584519311479667686627715728864057273036107427545351441992333703764148710086798963155916759426741193579376396522818496357335032139598670494577520161356987154136310419315797156777208723685881823376284494131513590136899083068033919977865483124290662185228944009736543594763905898717659641198560483737149541481094888019426062490884384838074953205628739379413727850315986194387378032781404281175230300985834217585463046424665894367379 done 40000000 iterations in time=44 sec. ans=4994097331495993759590792520652782896298040702842052804596091316575363414862676472297324459047461969855851762208911221321241374084825500814598324057817295157460163428748617431743371535373584519311479667686627715728864057273036107427545351441992333703764148710086798963155916759426741193579376396522818496357335032139598670494577520161356987154136310419315797156777208723685881823376284494131513590136899083068033919977865483124290662185228944009736543594763905898717659641198560483737149541481094888019426062490884384838074953205628739379413727850315986194387378032781404281175230300985834217585463046424665894367379 done 40000000 iterations in time=34 sec. Last fiddled with by R. Gerbicz on 20190503 at 20:19 Reason: small typo 
20190504, 00:47  #3  
"Robert Gerbicz"
Oct 2005
Hungary
1635_{10} Posts 
Quote:
errors. If you have an error in year 3 that goes undetected, you may waste the next 32 years of computing. Adi Shamir has proposed a slick means of checking your computation as you go, as follows. Pick a small (50bit) prime c, and perform the computation modulo cn rather than just modulo n. You can check the result modulo c whenever you like; this should be a extremely effective check on the computation modulo n as well." Here I'd use the extremely cheap Gerbicz error checking. 

20190504, 19:30  #4 
∂^{2}ω=0
Sep 2002
República de California
2^{2}×2,939 Posts 
Shamir's trick is fine as far as computing w.r.to general moduli goes, but yes, when are working with specialform moduli using fast DWTbased transform arithmetic, we now have better tools thanks to our local experts. :)
(I've just begun implementing your check for Mlucas v19.) 
20190505, 02:04  #5 
Jun 2003
1010101010101_{2} Posts 
Actually, the GEC's applicability is based on the form of the exponent. In this case the exponent is 2^x, so the computation is just a series of squarings, which means GEC is applicable regardless of the modulus. Would that be faster than Shamir's trick? I would think so  what's the overhead for GEC if we choose L=10^5 (so a GEC every 10^10 iterations), about 0.001% ?

20190505, 09:25  #6  
"Robert Gerbicz"
Oct 2005
Hungary
1635_{10} Posts 
Quote:
not using more limbs at modular squarings for (c*n). And this is unlikely with the large proposed c~50 bits prime, and with the 2046 bits n (yeah it hasn't got 2048 bits). That overhead is 2/L, so 0.002%. (assuming that mulmod and squaremod takes the same time). ps. you can call it Shamir's trick but I'm almost sure that it was very well known in 1999. 

20190505, 09:41  #7 
Sep 2016
17C_{16} Posts 
How did Rivest generate the puzzle parameters? Even if you knew the two factors of n, a CRT construction of each factor would only save you a factor of maybe 2.
Clearly I'm missing something very important. 
20190505, 09:58  #8  
Jun 2003
43×127 Posts 
Quote:
if we know the factors of c, we can compute eulerphi(c) and thus reduce the large exponent b to a much smaller size. This takes milliseconds. 

20190505, 16:22  #9 
Sep 2016
380_{10} Posts 

20190508, 12:50  #10  
May 2019
13 Posts 
Quote:
I tried with two GMP versions (one coming stock with Debian and one compiled from source) and I get 44 seconds for these 40 million iterations in both cases. My CPU is a Core i76700: it is not the K version. It turboboosts to 3.9 Ghz when only one core is used. I did this on my everyday workstation so at times more cores were used and hence my 6700 wouldn't turbo boost at 3.9 Ghz. Did you try this on a 6700 or 6700 K? It's a nice speedup you got there that said. EDIT: typo. I replaced one of the "7600" by "6700". EDIT 2: on my Core i76700 using R. Gerbicz' code I get about 910k sq/s. Simon Peffer's team's FPGA (a Xilinx vu9p) is getting about 15M sq/s (they'll have the solution by the 11th of May). There's a third team which is actually building an ASIC and they're using a FPGA to validate their ASIC design. Ballpark estimation from what I understood reading the emails: 10x improvement compared to the FPGA. So the ASIC team should have hardware solving this in a matter of days (as of opposed to 2 years' ish using good code and a fast machine). EDIT 3: I'm neither a cryptographer nor a number cruncher. I just happened to realize upon reading the problem and doing a few tests that it was possible to solve this before 2034 ; ) Last fiddled with by TacticalCoder on 20190508 at 13:26 

20190508, 13:36  #11 
"Ben"
Feb 2007
2^{2}×941 Posts 

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 