4 ms·

Read the paper. It tells you why they think it's better than that. And I think that has stood so far.

thaumasiotes 8y 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?
- simond_d 8y ago
  I hate it when people think they know better than the experts. Do you really think that if they could have made it run in parallel they wouldn't have? Get off your high horse and solve it yourself if you're so smart.
  - brianpgordon 8y ago
    Seems to me like a good-faith effort to understand. And respect for the experts isn't the same as unquestioningly accepting all of their assumptions.
- eru 8y ago
  > 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. Well, there's no mathematical proof. But physicists and judges would accept that there's lots of money and fame to be made breaking eg RSA, so countless people have tried and keep trying, but haven't come up with much good so far.
- BlackFly 8y ago
  The answer to your question is, "No, there is no proof." This is similar to the answer to, "Is there any proof that RSA is uncrackable?" The security is based upon the assumed hardness of certain mathematical problems.

> 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?

simond_d 8y ago
I hate it when people think they know better than the experts. Do you really think that if they could have made it run in parallel they wouldn't have? Get off your high horse and solve it yourself if you're so smart.
- brianpgordon 8y ago
  Seems to me like a good-faith effort to understand. And respect for the experts isn't the same as unquestioningly accepting all of their assumptions.
eru 8y ago
> 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. Well, there's no mathematical proof. But physicists and judges would accept that there's lots of money and fame to be made breaking eg RSA, so countless people have tried and keep trying, but haven't come up with much good so far.
BlackFly 8y ago
The answer to your question is, "No, there is no proof." This is similar to the answer to, "Is there any proof that RSA is uncrackable?" The security is based upon the assumed hardness of certain mathematical problems.