Re: Quantum Computers breaking ciphers
From: Paul Leyland (paul_at_leyland.vispa.com)
Date: 10 Oct 2004 10:47:12 +0100
Phil Carmody <firstname.lastname@example.org> writes:
> Paul Leyland <email@example.com> writes:
> > Phil Carmody <firstname.lastname@example.org> writes:
> > > That's a complete non-sequitur hodge-podge of an argument. How can
> > > you say "*IF* you have a candidate...", emphasis mine, and make the
> > > conclusion you do?
> > > The factoring algorithm is the thing that /gives/ you the candidate.
> > > If there's a chance that the factoring algorithm /fails/ to give you
> > > a candidate then it matters not a whit whether you could have verified
> > > it deterministically in P time.
> > Run the QC several times to generate factors in QP-time, testing each
> > result in P-time on a classical computer.
> > Your objection has been considered many times in the past.
> If it's possible for any of the 'several' times to fail, it's
> possible for all of them to fail. Lather rinse repeat. You can't
> get rid of non-determinism by repeating the test.
Correct, but you can expect to get an answer in polynomial time.
Your response is just as valid for, say, the NFS or QS run on a
conventional machine. It is possible that an arbitrarily long
sequence of dependencies will generate the trivial factorization but,
unless you are trying to factor a prime power, each dependency is
expected to find a non-trivial factorization with probability at least
Such nondeterminism doesn't deter anyone from using the NFS.
-- Hanging on in quiet desperation is the English way. The time is gone, the song is over. Thought I'd something more to say.