> Would it be overly conspiratorial to suggest that the CIA and NSA are in fact interested in a large-scale implementation of Shor's algorithm?

The only thing conspiratorial is that it wasn't mentioned in the article. Hmmmm.

I would be worried if they weren't interested in Shor's algorithm. That's something that fits their mandate at least.

Context: http://en.wikipedia.org/wiki/Shor%27s_algorithm

They would be derelict in their duty to NOT be very closely tracking the (open literature) state of the art in factorization. I.e., it's not a conspiracy, it's their job, and it always has been.

I also presume they have people working to keep abreast of the state of the art in secret work of other countries.

Can anyone provide an explanation of this in layman's terms? I took a look at wikipedia but am having a hard time wrapping my head around it..

A lot of public key cryptography methods used in the real world are based on the fact that factoring really big numbers is computationally unfeasible. Shor's algorithm makes it feasible, but it's a quantum algorithm that can't be run on a classical computer. Basically, alot of stuff won't be secure anymore when it's feasible to run Shor's algorithm.

But would new forms of currently-infeasible encryption become possible at the same time? Many forms of encryption have fallen over the years as technology and mathematics have advanced; while at the same time better encryption methods have been developed.

Oh, of course. The dance between defense and offense will continue as usual. However, there may be a window of time where a lot of services are left vulnerable in the transition.