4 ms·

I see this problem as simultaneously a cryptographic challenge and a DevOps one. So mine isn't a cryptographic question, but I'd love to know what steps you to

by pryce 7y ago

I see this problem as simultaneously a cryptographic challenge and a DevOps one. So mine isn't a cryptographic question, but I'd love to know what steps you took to ensure integrity and uptime of your consumer i7 hardware, and capture of each partial step of the solution, while you ran your algorithm. EDIT: also, congratulations! (How did I leave that out!?)

TacticalCoder 7y ago
I'm no cryptographer so it's good news you don't have any cryptographic question ; ) I basically used my everyday workstation. There were 79 trillions operations to be made and I'd save the intermediate result every 1 billion result (so approximately every 22 minutes I'd save a result). The computation cannot be parallelized and the i7 I was using has four cores. So basically instead of turning it every night off I'd simply leave it running 24/7. I'd simply backup the files with the intermediate results once in a while. I rebooted the computer about 50 times in 4 years and during those 4 years during about 3 and half years it was computing towards the solution. But I coded (totally unrelated things), compiled things from source, browsed the web, did my email, etc. from the very workstation which computed the solution. The computation is easy to relaunch from any intermediate step. Thanks for the congrats!
- nixpulvis 7y ago
  Wow, this is awesome! Great job computing it. This reminds me of a time during college a professor gave us an extra credit assignment to essentially find prime factoring large numbers (classic problem). I had come up with a pretty bad solution, but thought it might just finish in time for the deal line if I left it running all week. Of course a transformer blew up the day before the deadline, and I never knew... chances are my program would have never terminated :P
- thaumasiotes 7y ago
  > The computation cannot be parallelized Is there a proof of this somewhere? Operations that seem vaguely similar, like doubling repeatedly, can be easy to "parallelize".
  - TacticalCoder 7y ago
    The puzzle is based on a paper from 1996 by Rivest, Shamir and Wagner: https://people.csail.mit.edu/rivest/pubs/RSW96.pdf https://people.csail.mit.edu/rivest/pubs/RSW96.pdf Each step depends on the result of the previous step. I don't know of any claim that the crypto/maths behind the paper do not hold. You can use a FPGA or build an ASIC: but as far as I know as long as the crypo in this paper hold, it's not parallelizable.
    - thaumasiotes 7y ago
      > Each step depends on the result of the previous step. But this doesn't mean anything. If I said to take a number and add 1 eighty trillion times, each step would depend on the result of the previous step, but obviously it would be unnecessary to actually compute each step.
      - scarejunba 7y ago
        Read the paper. It tells you why they think it's better than that. And I think that has stood so far.
        thaumasiotes 7y ago
        > Read the paper. It tells you why they think it's better than that. OK, I read the paper. This is the entire discussion of the inherent difficulty of repeated squaring: > More importantly, repeated squaring seems to be an "intrinsically sequential" process. We know of no obvious way to parallelize it to any large degree. (A small amount of parallelization may be possible within each squaring.) Having many computers is no better than having one. (But having one fast computer is better than one slow one.) The degree of variation in how long it might take to solve the puzzle depends on the variation in the speed of single computers, and not on one's total budget. I see two problems here: (1) This is a purely conclusory argument, suggesting that a better response would have been a simple "no, there's no proof". (2) This does not even attempt to address the question I posed, which was whether it is necessary to compute the intermediate results in order to compute the final result. In fact, we know that the intermediate results are not necessary to compute the final result, because that is how the message gets enciphered in the first place. It can be done by factoring the modulus, and obviously there is no proof that that is difficult to do. But beyond that, it also isn't immediately obvious that it must necessarily be impossible to compute the final result directly by means that don't require factoring the modulus. It is possible that somewhere in the literature on Blum Blum Shub this question has been analyzed, but that goes a bit beyond your suggestion to "read the paper". So, I'm stumped. Tell me what you saw in the paper that you thought would answer my question?
- basetop 7y ago
  That's amazing dedication. Congrats. Did your power bill increase noticably?
  - TacticalCoder 7y ago
    No it really didn't. I think I mentioned here elsewhere in a comment but I use an Intel Core-i7 6700 "non K": so the version that is not meant to be overclocked and which Intel rates as having a max TDP of 65W. And this would be with the four cores running. I don't know the TDP / power consumption when it's turbo-boosting at 3.9 or 4.0 Ghz (when one or two cores are at full speed on the 6700, it goes from 3.4 to 3.9 or 4.0 on these cores). Basically I like my workstation to be quiet. Really very quiet: as in I can only hear it if I put my ear on the tower. So I never have ultra power hungry CPUs. I don't game so no GPU besides the integrated one. A M.2 SSD which consumes next to nothing. Power bill probably did increase a bit but honestly it was lost in the noise: I definitely didn't notice anything : )
TacticalCoder 7y ago
As for the uptime it's a pretty reliable machine: I'm running the i7-6700 (non K, so non overclocked) version. Intel lists it at 65W max TDP but that'd be with all the cores at 100% I guess. It's a 3.4 Ghz CPU turbo-boosting when only one core is at 100% to 4.0 Ghz on that one core. OS is Debian stretch: it's rock solid in my experience. It was rebooted on average once a month (I switched country, there were black outs, I upgraded the OS, etc.) but there have been stretches where it was up for several months in a row, happily cranking!

by pryce 7y ago

TacticalCoder 7y ago

I'm no cryptographer so it's good news you don't have any cryptographic question ; ) I basically used my everyday workstation. There were 79 trillions operations to be made and I'd save the intermediate result every 1 billion result (so approximately every 22 minutes I'd save a result). The computation cannot be parallelized and the i7 I was using has four cores. So basically instead of turning it every night off I'd simply leave it running 24/7. I'd simply backup the files with the intermediate results once in a while. I rebooted the computer about 50 times in 4 years and during those 4 years during about 3 and half years it was computing towards the solution. But I coded (totally unrelated things), compiled things from source, browsed the web, did my email, etc. from the very workstation which computed the solution. The computation is easy to relaunch from any intermediate step. Thanks for the congrats!

nixpulvis 7y ago
Wow, this is awesome! Great job computing it. This reminds me of a time during college a professor gave us an extra credit assignment to essentially find prime factoring large numbers (classic problem). I had come up with a pretty bad solution, but thought it might just finish in time for the deal line if I left it running all week. Of course a transformer blew up the day before the deadline, and I never knew... chances are my program would have never terminated :P
thaumasiotes 7y ago
> The computation cannot be parallelized Is there a proof of this somewhere? Operations that seem vaguely similar, like doubling repeatedly, can be easy to "parallelize".
- TacticalCoder 7y ago
  The puzzle is based on a paper from 1996 by Rivest, Shamir and Wagner: https://people.csail.mit.edu/rivest/pubs/RSW96.pdf https://people.csail.mit.edu/rivest/pubs/RSW96.pdf Each step depends on the result of the previous step. I don't know of any claim that the crypto/maths behind the paper do not hold. You can use a FPGA or build an ASIC: but as far as I know as long as the crypo in this paper hold, it's not parallelizable.
  - thaumasiotes 7y ago
    > Each step depends on the result of the previous step. But this doesn't mean anything. If I said to take a number and add 1 eighty trillion times, each step would depend on the result of the previous step, but obviously it would be unnecessary to actually compute each step.
    - scarejunba 7y ago
      Read the paper. It tells you why they think it's better than that. And I think that has stood so far.
      - thaumasiotes 7y ago
        > Read the paper. It tells you why they think it's better than that. OK, I read the paper. This is the entire discussion of the inherent difficulty of repeated squaring: > More importantly, repeated squaring seems to be an "intrinsically sequential" process. We know of no obvious way to parallelize it to any large degree. (A small amount of parallelization may be possible within each squaring.) Having many computers is no better than having one. (But having one fast computer is better than one slow one.) The degree of variation in how long it might take to solve the puzzle depends on the variation in the speed of single computers, and not on one's total budget. I see two problems here: (1) This is a purely conclusory argument, suggesting that a better response would have been a simple "no, there's no proof". (2) This does not even attempt to address the question I posed, which was whether it is necessary to compute the intermediate results in order to compute the final result. In fact, we know that the intermediate results are not necessary to compute the final result, because that is how the message gets enciphered in the first place. It can be done by factoring the modulus, and obviously there is no proof that that is difficult to do. But beyond that, it also isn't immediately obvious that it must necessarily be impossible to compute the final result directly by means that don't require factoring the modulus. It is possible that somewhere in the literature on Blum Blum Shub this question has been analyzed, but that goes a bit beyond your suggestion to "read the paper". So, I'm stumped. Tell me what you saw in the paper that you thought would answer my question?
basetop 7y ago
That's amazing dedication. Congrats. Did your power bill increase noticably?
- TacticalCoder 7y ago
  No it really didn't. I think I mentioned here elsewhere in a comment but I use an Intel Core-i7 6700 "non K": so the version that is not meant to be overclocked and which Intel rates as having a max TDP of 65W. And this would be with the four cores running. I don't know the TDP / power consumption when it's turbo-boosting at 3.9 or 4.0 Ghz (when one or two cores are at full speed on the 6700, it goes from 3.4 to 3.9 or 4.0 on these cores). Basically I like my workstation to be quiet. Really very quiet: as in I can only hear it if I put my ear on the tower. So I never have ultra power hungry CPUs. I don't game so no GPU besides the integrated one. A M.2 SSD which consumes next to nothing. Power bill probably did increase a bit but honestly it was lost in the noise: I definitely didn't notice anything : )

TacticalCoder 7y ago

As for the uptime it's a pretty reliable machine: I'm running the i7-6700 (non K, so non overclocked) version. Intel lists it at 65W max TDP but that'd be with all the cores at 100% I guess. It's a 3.4 Ghz CPU turbo-boosting when only one core is at 100% to 4.0 Ghz on that one core. OS is Debian stretch: it's rock solid in my experience. It was rebooted on average once a month (I switched country, there were black outs, I upgraded the OS, etc.) but there have been stretches where it was up for several months in a row, happily cranking!