If there is some kind of connection between prime numbers, wouldn't a lot of the current work in encryption be thrown out?
Unlikely. The recent work doesn't improve our ability to factor large integers, the key to modern cryptography. If someone created a function that instantly produced the prime factors for large integers without the present difficult process, that would change everything, but that's not a likely outcome.
The next real challenge to modern cryptography isn't this work, but quantum computing. If quantum computing came to full flower with no obstacles sometime in the future, that would represent a basic change because it would perform an end run around the present computational difficulties that assure the security and reliability of our present methods.
I found some info here, but I didn't get enough out of it to answer my question directly. I think the answer is "Well theoretically, but it's complicated":
http://stackoverflow.com/questions/2768807/quantum-computing...
http://en.wikipedia.org/wiki/Quantum_computer#Potential
http://en.wikipedia.org/wiki/Shor%27s_algorithm
http://en.wikipedia.org/wiki/Post-quantum_cryptography
[...] most currently popular public-key cryptosystems
rely on the integer factorization problem or discrete
logarithm problem, both of which would be easily solvable
on large enough quantum computers using Shor's algorithm.
Even though current publicly known experimental quantum
computing is nowhere near powerful enough to attack real
cryptosystems, many cryptographers are researching new
algorithms, in case quantum computing becomes a threat in
the future.Shor's algorithm, on the other hand, runs in O((logN)^3). For an idea of the difference, log(64)^3 = 216, log(1024)^3 = 1000.
So Shor's algorithm could be used to very quickly factorize large numbers and would effectively break RSA. We just need a quantum computer, which as far as we know nobody has yet.
There will probably be significant warning before quantum computers exist which can break RSA. In that time it will probably become the norm to no longer use algorithms which are rendered obsolete by quantum computers.
Yes, but it's a big "if". There are many obstacles that stand in the way of quantum computing on a large scale, in fact some believe it will never be possible to maintain the delicate conditions required to perform quantum computation on a large scale.
The reason quantum computing could outperform conventional computation is because a quantum computer would, in a manner of speaking, process all possible problem statements at once, in parallel, and arrive at the best solution just as though only one problem statement had been processed. I know that may be difficult to imagine, but so is quantum. About quantum theory, John Wheeler said, "If you are not completely confused by quantum mechanics, you do not understand it."
Suffice it to say that quantum computing on a scale sufficient to pose a threat to public-key cryptosystems is not just around the corner.
As for the specifics, I believe we have working 4-qbit quantum computers, and shor's algorithm has been successfully applied to calculate that 15=3x5. But current approaches do indeed seem unlikely to scale up to 1024 qbits.
Yes, if you examine the mathematics that's true, but if you examine the physics it's not true. The problem doesn't lie with algorithm design, the problem lies with putting them into practice in actual physical computers.
> QM in general is really pretty simple and even obvious if you ignore the silly mythology and just follow the math.
On the contrary, not at all simple if one must try create an actual physical realization.
This is not to suggest that the problems won't be overcome, only that they're more formidable than describing how easy it is in principle.