What about Shor’s algorithm? Is this not at least in theory a easy way to break RSA. Only the practical barrier of building a quantum computer capable of cracking practical encryption remains.
Shor’s algorithm was found/invented after RSA so for close for two decades there was no known theoretical solution. That did not mean that it was not possible however.
Many of the people who thought it was impossible to break RSA in polynomial time were arrogant, they thought they understood the world much better then they actual did. Many of the people who thought that it was obvious that RSA would one day be solved in polynomial time were also arrogant. You are right it is not possible to decide the answer one way or another, nature can not be bullied. It is however often necessary to take actions before you can not for sure one way or another. So your colleague probably internally transformed his best guess in to a ‘fact’ so he could act on it. Or maybe it transformed from guess in thought to an utterance of fact out of subconsciousness tendency because it sounds more convincing to most of the audiences he/she has talked to.
To my knowledge Shor’s algorithm is currently accepted as correct the exact requirements for a practical quantum computer that can solve today’s RSA encryption is still being explored.
Many of the people who thought it was impossible to break RSA in polynomial time were arrogant, they thought they understood the world much better then they actual did. Many of the people who thought that it was obvious that RSA would one day be solved in polynomial time were also arrogant.
Could you quote some of those people? I’m not aware of a lot of knowledgeable people making unwarrantedly strong assertions.
My assertion was also not specific to people knowledgeable in the field, just like the op’s colleague is not very knowledgable in RSA(at least I had assumed so). I consider the probability of a non-expert having said this to be to be close to 100%.
Be forewarned I am not an expert in the feild, but here are some interesting tidbits:
Thesis (Quantitative Church’s thesis). Any physical computing device can be simulated by a Turing machine in a number of steps polynomial in the resources used by the computing device”
Then:
If the precision of a quantum computer is large enough to make it more powerful than a classical
computer, …
edit:
Shor is suggesting that quantum computers break the Church thesis which implied that for any device it was impossible to solve RSA in poly time.
end edit.
Note that AFAIK Church did not state this “Quantitative Church’s thesis”—it’s hard to be sure because of the paywall, but I’d guess that this paper was the first to explicitly state it, and it did so in order to argue that it may not be true.
I could not tell which paper you are talking about. The paper I posted? It is not behind any pay wall for me. If not the paper I post which paper are you talking about I can try to look at it at work latter.
Don’t know what went wrong there—I have the paper now. Turns out I’m quite wrong, this idea is credited to:
P. van Emde Boas (1990), Machine models and simulations, in Handbook of Theoretical Computer Science, Vol. A, J. van Leeuwen, ed., Elsevier, Amsterdam, pp. 1–66.
What about Shor’s algorithm? Is this not at least in theory a easy way to break RSA. Only the practical barrier of building a quantum computer capable of cracking practical encryption remains.
Shor’s algorithm was found/invented after RSA so for close for two decades there was no known theoretical solution. That did not mean that it was not possible however.
Many of the people who thought it was impossible to break RSA in polynomial time were arrogant, they thought they understood the world much better then they actual did. Many of the people who thought that it was obvious that RSA would one day be solved in polynomial time were also arrogant. You are right it is not possible to decide the answer one way or another, nature can not be bullied. It is however often necessary to take actions before you can not for sure one way or another. So your colleague probably internally transformed his best guess in to a ‘fact’ so he could act on it. Or maybe it transformed from guess in thought to an utterance of fact out of subconsciousness tendency because it sounds more convincing to most of the audiences he/she has talked to.
To my knowledge Shor’s algorithm is currently accepted as correct the exact requirements for a practical quantum computer that can solve today’s RSA encryption is still being explored.
Could you quote some of those people? I’m not aware of a lot of knowledgeable people making unwarrantedly strong assertions.
My assertion was also not specific to people knowledgeable in the field, just like the op’s colleague is not very knowledgable in RSA(at least I had assumed so). I consider the probability of a non-expert having said this to be to be close to 100%.
Be forewarned I am not an expert in the feild, but here are some interesting tidbits:
Then:
edit: Shor is suggesting that quantum computers break the Church thesis which implied that for any device it was impossible to solve RSA in poly time. end edit.
Both from quotes are from “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”—Peter W. Shor
Note that AFAIK Church did not state this “Quantitative Church’s thesis”—it’s hard to be sure because of the paywall, but I’d guess that this paper was the first to explicitly state it, and it did so in order to argue that it may not be true.
I could not tell which paper you are talking about. The paper I posted? It is not behind any pay wall for me. If not the paper I post which paper are you talking about I can try to look at it at work latter.
Don’t know what went wrong there—I have the paper now. Turns out I’m quite wrong, this idea is credited to:
P. van Emde Boas (1990), Machine models and simulations, in Handbook of Theoretical Computer Science, Vol. A, J. van Leeuwen, ed., Elsevier, Amsterdam, pp. 1–66.
Same reaction here. Since it is physically possible to break RSA, it seems obvious to me that RSA will be broken… eventually.
Barring collapse of technological civilization/technological stagnation/human extinction.