The Long-Term Future of the Cryptography Policy Debate

[Jeffrey Goldberg]

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

On Mon, 9 Mar 1998, Peter Dare wrote:

> Can I just summarise again my original point:
> 
> Quantum computers will be practical propositions within decades or possibly
> years.
> 
> Quantum computers are massively parallel. [...]

I have not read any of the primary sources about quantum computing, so
what I am going to say is pure prejudice.  If someone who knows about
these things and has thought about these things tells me I am wrong,
I will accept that.

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?

-j   

--
Jeffrey Goldberg                +44 (0)1234 750 111 x 2826
 Cranfield Computer Centre      FAX         751 814
 J.Goldberg@Cranfield.ac.uk     http://WWW.Cranfield.ac.uk/public/cc/cc047/
Relativism is the triumph of authority over truth, convention over justice.