publius

2013-Jun-10, 07:06 AM

From stuff I've been reading, it is said that a quantum computer of enough power would be able to easily break RSA public key encryption. If anyone is knowledgable on this business, would you care to give me the Cliff Notes version of this works? The stuff I read is either too dumbed down or not dumbed down enough for me :)

I know it has to do with factoring of large prime numbers, and the quantum computer can do the required numerical drudgery very fast (sort of doing it all at once) via some very clever tricks. Supposedly this cuts the time required from exponential (or near exponential) to polynomial time, ie O(N^3) rather than O(e^N).

If someone would just sort of run through the process of how we would "crack" something doing this, I'd appreciate it. And, and I'm assuming this has to be true, is there a process/method where the O time would be still be ridiculously large for a quantum computer and not ridiculously large for the encrypting system that one could be safe?

I know it has to do with factoring of large prime numbers, and the quantum computer can do the required numerical drudgery very fast (sort of doing it all at once) via some very clever tricks. Supposedly this cuts the time required from exponential (or near exponential) to polynomial time, ie O(N^3) rather than O(e^N).

If someone would just sort of run through the process of how we would "crack" something doing this, I'd appreciate it. And, and I'm assuming this has to be true, is there a process/method where the O time would be still be ridiculously large for a quantum computer and not ridiculously large for the encrypting system that one could be safe?