mersenneforum.org  

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

Reply
 
Thread Tools
Old 2019-05-08, 13:47   #12
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101111011102 Posts
Default

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

2·23·137 Posts
Default

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

So what is the answer? Do tell.
retina is offline   Reply With Quote
Old 2019-05-08, 13:50   #14
axn
 
axn's Avatar
 
Jun 2003

10100001110112 Posts
Default

Quote:
Originally Posted by TacticalCoder View Post
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


Quote:
Originally Posted by TacticalCoder View Post
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.
axn is offline   Reply With Quote
Old 2019-05-08, 14:21   #15
TacticalCoder
 
May 2019

D16 Posts
Default

Quote:
Originally Posted by retina View Post
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 is offline   Reply With Quote
Old 2019-05-08, 14:33   #16
TacticalCoder
 
May 2019

13 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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.
TacticalCoder is offline   Reply With Quote
Old 2019-05-08, 16:02   #17
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

960910 Posts
Default

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?
Batalov is offline   Reply With Quote
Old 2019-05-08, 16:37   #18
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32×5×71 Posts
Default

Quote:
(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.
ATH is offline   Reply With Quote
Old 2019-05-08, 18:47   #19
TacticalCoder
 
May 2019

13 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
TacticalCoder is offline   Reply With Quote
Old 2019-05-08, 23:43   #20
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

209C16 Posts
Default

Quote:
Originally Posted by TacticalCoder View Post
Hi there, I'm the one who found the solution.
Welcome to the forum!


How did you end up here?


Xyzzy is offline   Reply With Quote
Old 2019-05-09, 14:34   #21
TacticalCoder
 
May 2019

13 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
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 ; )
TacticalCoder is offline   Reply With Quote
Old 2019-05-09, 17:37   #22
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

10,103 Posts
Default

Cool story.

Welcome to the Forum.


Uncwilly is online now   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 15:41.


Mon Nov 29 15:41:34 UTC 2021 up 129 days, 10:10, 0 users, load averages: 1.80, 1.46, 1.34

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.