The Long-Term Future of the Cryptography Policy Debate

[Nicolas D Fortescue]

On Mon, 9 Mar 1998, Jeffrey Goldberg wrote:

> My feeling is that this discussion better belongs on sci.crypt than
> on this list, but until the list manager intervenes, I will continue.

You're probably correct, but as a question was asked...

> My feeling is that quantum computing is a red herring wrt to factoring
> and other code breaking because (I suspect) moves the complexity from
> the running of the algorithm to the construction of the algorithm.  The
> analogy I want to make is to very naive proposal that one precompile
> a complete list of primes in the relevant range and then factor in
> close to linear time.
> 
> All that does is move the complexity from the run time portion to
> building the algorithm.  I suspect that the number of nodes needed
> for a quantum computer to factor may grow very quickly with the size
> of the number being factored, so that in the end quantum computing
> will not offer a less complex way of factoring.
> 
> Am I wrong about this?  And what should I read to find out why?

You are wrong. A quantum compututer can set up a superposition of 2^n
states in linear time. The best introduction I know (but then I'm a biased
local :) is:

http://eve.physics.ox.ac.uk/NewWeb/Research/Tutorial/recherche.html

which is linked to from:

http://eve.physics.ox.ac.uk/QChome.html

a good place to start for all things quantum.

Nick