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

[R. Gerbicz]

Originally Posted by TacticalCoder

Hi there, I'm the one who found the solution. I tried your code on my Core i7-6700 and I do not get 34 seconds for the 40 million iterations: I get 44 seconds, not 34 seconds.

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 i7-6700: it is not the K version. It turbo-boosts to 3.9 Ghz when only one core is used.

Welcome to the forum!
Yes, I've got also core i7-6700, so not the K version (there was not much difference in the pricing between these two),
used Corsair 2x8GB DDR4 2400 MHz, and the most recent gmp-6.1.2 .

Here it is a recent rerun, to see also my optimized compiler flags:

gerbicz@gerbicz-MS-7972:~/gmp-6.1.2$ gcc -mtune=skylake -march=skylake -fomit-frame-pointer -flto -frename-registers -mavx2 -m64 -O2 -o puzzle puzzle.c -lgmp
gerbicz@gerbicz-MS-7972:~/gmp-6.1.2$ ./puzzle
Read n=6314466083072888893799357126131292332363298818330841375588990772701957128924885547308446055753206513618346628848948088663500368480396588171361987660521897267810162280557475393838308261759713218926668611776954526391570120690939973680089721274464666423319187806830552067951253070082020241246233982410737753705127344494169501180975241890667963858754856319805507273709904397119733614666701543905360152543373982524579313575317653646331989064651402133985265800341991903982192844710212464887459388853582070318084289023209710907032396934919962778995323320184064522476463966355937367009369212758092086293198727008292431243681 has 2046 bits.
ans=4994097331495993759590792520652782896298040702842052804596091316575363414862676472297324459047461969855851762208911221321241374084825500814598324057817295157460163428748617431743371535373584519311479667686627715728864057273036107427545351441992333703764148710086798963155916759426741193579376396522818496357335032139598670494577520161356987154136310419315797156777208723685881823376284494131513590136899083068033919977865483124290662185228944009736543594763905898717659641198560483737149541481094888019426062490884384838074953205628739379413727850315986194387378032781404281175230300985834217585463046424665894367379
done 40000000 iterations in time=42 sec.
ans=4994097331495993759590792520652782896298040702842052804596091316575363414862676472297324459047461969855851762208911221321241374084825500814598324057817295157460163428748617431743371535373584519311479667686627715728864057273036107427545351441992333703764148710086798963155916759426741193579376396522818496357335032139598670494577520161356987154136310419315797156777208723685881823376284494131513590136899083068033919977865483124290662185228944009736543594763905898717659641198560483737149541481094888019426062490884384838074953205628739379413727850315986194387378032781404281175230300985834217585463046424665894367379
done 40000000 iterations in time=33 sec.
gerbicz@gerbicz-MS-7972:~/gmp-6.1.2$

[retina]

With all the publicity I still haven't seen the result posted anywhere.

So what is the answer? Do tell.

[axn]

Originally Posted by TacticalCoder

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 ; )

A 6700 isn't that much faster than the previous generations, so somebody could've solved this maybe 3-4 years back if they had started on a Sandy Bridge around 2012

Originally Posted by TacticalCoder

EDIT 2: on my Core i7-6700 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).

I wonder what sort of speed is achievable on a Skylake-X using custom AVX-512 sqrmod.

[TacticalCoder]

Originally Posted by retina

With all the publicity I still haven't seen the result posted anywhere.

So what is the answer? Do tell.

Oh there's an embargo on the solution until the 15th of May. There's two reasons for that: there's a bit more drama showing the solution at the MIT just before opening the "time capsule" and then the second team, led by Simon Peffers, do not have the answer yet. They should have the answer by the 11th or 12th of May.


It's just a little sentence and, as the problem states, the value of "b" which allows to find one of the two primes (and hence the second one too of course).


I think I'll be the one revealing the solution (I'm working on my slides atm, hence the question re- the speed that's achievable).


On to test the code with the correct gcc parameters...

[TacticalCoder]

Originally Posted by R. Gerbicz

Welcome to the forum!
Yes, I've got also core i7-6700, so not the K version (there was not much difference in the pricing between these two)

Thanks! I bought the 6700 back then because of it's rated max TDP of 65W: it's my everyday workstation and I like it to be totally quiet.


My RAM is a bit slower (2133 as opposed to your 2400) but is this hitting the RAM a lot?



I tested with the exact same compilation parameters to gcc and it's still taking 44 seconds here.



Then there's the GMP version. I'll test with the latest GMP. Now I started testing in late 2014 and computing in 2015: I don't know if GMP got faster meanwhile.


I'm using Linux and I can clearly see the core turbo-boosting to 3.9 Ghz or 4.0 Ghz so I think it's not related the CPU governor.



I'll try to find the time to test with the latest GMP version.

[Batalov]

It is interesting that the n value is in factordb.com for some time (before last database cleanup on 11/4/2018, as it self-reports), so someone did enter it (by reading the puzzle's code). Or is this a number that is reused from some other linked problem, does anyone know?

[ATH]

(The extra information is a seed value b, such that
5^b (mod 2^1024) is just below a prime factor of n.)

I assume the b-value is very big or this could be brute forced to find the factors of n.

[TacticalCoder]

Originally Posted by ATH

I assume the b-value is very big or this could be brute forced to find the factors of n.

It's a bit more than 200 bits.

[Xyzzy]

Originally Posted by TacticalCoder

Hi there, I'm the one who found the solution.

Welcome to the forum!


How did you end up here?

[TacticalCoder]

Originally Posted by Xyzzy

How did you end up here?

Well now that LCS35 is solved and I learned I'll be talking at the MIT and showing slides, I'm trying to find why there's been such a difference between the 35 years expected before solving the puzzle and the 3.3 years it actually took me (switch from 32 to 64 bit, less cycles per instructions, better algorithms, initial estimate only at most 15% off, etc.)



I'm also doing my own "revue de presse" (searching for the articles talking about that problem) and I stumbled upon the message saying that on the same hardware as I used it's actually doable in 2.16 years (I could speedup but couldn't reproduce the same speedup: maybe because of my RAM which is slower but that looks weird ?) so I created an account to ask questions about that :)


And, well, I'm quite the number cruncher too now ; )

[Uncwilly]

Cool story.

Welcome to the Forum.