From: Eliezer S. Yudkowsky (sentience@pobox.com)
Date: Thu Sep 27 2001 - 17:32:10 MDT
hal@finney.org wrote:
>
> The largest key sizes in common use today are 256 bits. If quantum
> computers become possible they effectively halve the key length, so it
> would require 2^128 operations to brute force such a key.
Are you sure about this? I know that in the general case it's been
demonstrated that you can get at least an O(2^N) to O(2^(N/2)) speedup on
generic searches. But I was under the impression that factoring was not a
generic search, and that the problem required 3N qubits to directly crack
an N-bit number (in constant time?). Unfortunately I cannot remember my
source on this at all, so it could just be a figment of my imagination.
-- -- -- -- --
Eliezer S. Yudkowsky http://singinst.org/
Research Fellow, Singularity Institute for Artificial Intelligence
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 08:11:01 MST