Re: Steganography

From: Eliezer S. Yudkowsky (
Date: Thu Sep 27 2001 - 17:32:10 MDT 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
Research Fellow, Singularity Institute for Artificial Intelligence

This archive was generated by hypermail 2b30 : Fri Oct 12 2001 - 14:40:58 MDT