[8179] in cryptography@c2.net mail archive
Shor's Alg and factoring
daemon@ATHENA.MIT.EDU (Ben Nagy)
Sun Dec 3 21:21:13 2000
Message-ID: <F6CE7C91209AD411A10F00508BCA37E80E3129@adebdc001.sa.marconi.com.au>
From: Ben Nagy <ben.nagy@marconi.com.au>
To: "'cryptography@c2.net'" <cryptography@c2.net>
Date: Mon, 4 Dec 2000 12:48:18 +1030
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
G'day,
This simply must be an FAQ, but I've searched the archives of the list and
several others without a clear result.
We know that Shor's Algorithm (on a QC) reduces the complexity of factoring
/ discrete logs from exp to poly time. Does anyone have a feel for what this
does to key lifetime calculations / risk assessment? Poly time does not
neccessarily beat exp-time in the real world - it all depends on
contstants...
Yes, I know that it might not even be possible to build a QC with a large
enough qbit register, and yes I know that factoring might not actually be
exp time on "normal" computers (but we all think/hope it is). All I'm trying
to clarify is - assuming that someone builds a 1024 qbit QC, how long would
it take to factor a 1024 bit composite? Or, more on point, do 2048-bit and
4096-bit composites because computationally tractable?
Cheers,
--
Ben Nagy
Marconi Services
Network Integration Specialist
Mb: +61 414 411 520 PGP Key ID: 0x1A86E304
