# Re: Quantum Computers breaking ciphers

**From:** Paul Leyland (*paul_at_leyland.vispa.com*)

**Date:** 10/10/04

**Next message:**Lassi Hippeläinen: "Re: new /dev/random"**Previous message:**Phil Carmody: "Re: Fully Exponential ECDLP Running Time"**In reply to:**Phil Carmody: "Re: Quantum Computers breaking ciphers"**Next in thread:**Bill Unruh: "Re: Quantum Computers breaking ciphers"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: 10 Oct 2004 10:47:12 +0100

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

*> Paul Leyland <paul@leyland.vispa.com> writes:
*

*> > Phil Carmody <thefatphil_demunged@yahoo.co.uk> 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

1/2.

Such nondeterminism doesn't deter anyone from using the NFS.

Paul

-- Hanging on in quiet desperation is the English way. The time is gone, the song is over. Thought I'd something more to say.

**Next message:**Lassi Hippeläinen: "Re: new /dev/random"**Previous message:**Phil Carmody: "Re: Fully Exponential ECDLP Running Time"**In reply to:**Phil Carmody: "Re: Quantum Computers breaking ciphers"**Next in thread:**Bill Unruh: "Re: Quantum Computers breaking ciphers"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]