3 ms·

He's not wrong, but that doesn't make him right.

by eximius 10y ago

Animats 10y ago
He makes the good point that factoring is already below exponential time, and there's been progress over the years in speeding it up. Even if someone doesn't develop a polynomial time algorithm, there still could be substantial progress. There's also the possibility of new algorithms which are fast for some products of two primes, but not all. There are lots of problems, such as linear programming, where the worst case is exponential but the average case is far faster. Even something that allowed easy factoring of only 1% of products of two primes would be useful to an attacker.
- eximius 10y ago
  I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. If quantum stuff comes first, then we can go to lattice based systems (which are the leading candidate as far as I know - please correct me otherwise, I am familiar with lattice based systems but have not done research for a better base). If factoring is solved first, we can stick with elliptic curves.
  - coldtea 10y ago
    >I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. That's hardly a consolation, since all that we've encrypted and shared until then will be trivial to break as long as people have them in encrypted form (which is very easy to do).
    - eximius 10y ago
      That is sort of inevitable, I think. Best case, it is never broken and we never get quantum computers, but I hope that doesn't come to pass. So the next best case is that most of the details recovered by such breakage are irrelevent to those still alive. I think thats far more likely anyway.
coldtea 10y ago
He doesn't maintain he is right, so that's beside the point. His main claim is that others that say it's hard are not necessarily right either, and have no proof for that.

He's not wrong, but that doesn't make him right.

by eximius 10y ago

He's not wrong, but that doesn't make him right.

He makes the good point that factoring is already below exponential time, and there's been progress over the years in speeding it up. Even if someone doesn't develop a polynomial time algorithm, there still could be substantial progress. There's also the possibility of new algorithms which are fast for some products of two primes, but not all. There are lots of problems, such as linear programming, where the worst case is exponential but the average case is far faster. Even something that allowed easy factoring of only 1% of products of two primes would be useful to an attacker.

eximius 10y ago
I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. If quantum stuff comes first, then we can go to lattice based systems (which are the leading candidate as far as I know - please correct me otherwise, I am familiar with lattice based systems but have not done research for a better base). If factoring is solved first, we can stick with elliptic curves.
- coldtea 10y ago
  >I'm not too terribly worried. There are enough efforts to look for post-quantum crypto algorithms that I think by the time we come up with something that actually threatens factoring, we'll have alternatives. That's hardly a consolation, since all that we've encrypted and shared until then will be trivial to break as long as people have them in encrypted form (which is very easy to do).
  - eximius 10y ago
    That is sort of inevitable, I think. Best case, it is never broken and we never get quantum computers, but I hope that doesn't come to pass. So the next best case is that most of the details recovered by such breakage are irrelevent to those still alive. I think thats far more likely anyway.

coldtea 10y ago

He doesn't maintain he is right, so that's beside the point. His main claim is that others that say it's hard are not necessarily right either, and have no proof for that.