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 2b30 : Fri Oct 12 2001 - 14:40:58 MDT