Quantum computing

[Robert J. Hansen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

> On 200704172359, Robert J. Hansen wrote:
>> 1.  We are unlikely to ever be able to brute-force a 256-bit
>> keyspace.  Ever.  Not until computers are made of something other
>> than matter, occupy something other than space, run on something
>> other than energy, according to rules other than physics.
>
> I was under the impression that quantum computers were about to  
> provide
> a break in factorization. From quick grep on Wikipedia, I find that:

They've been "about to provide" a break in factorization for the last  
30 years.

> However, I assume you know what you talk about, when you say that we
> aren't likely to factor 256-bit-numbers ever. So please restate  
> that --
> even in the face of quantum computers -- we won't ever factor 256 bit
> numbers.

We're already factoring 256-bit numbers.  Fortunately, I didn't claim  
256-bit composites would forever be secure.  I claimed 256-bit  
keyspace searches would be secure.

Keyspace search is a different set of problems than factorization.   
For a brute-force search the best we can do is Grover's quantum  
database algorithm, which reduces it down to an equivalent 128-bit  
keyspace.  From there we use quantum thermodynamics--namely the  
Margolus-Levitin theorem--to get some reasonable bounds on how much  
time, energy, etc., are required to do it.




-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGJiWiAAoJELcA9IL+r4EJCTcH/RUOxI6RNuuu2WaCpAeJLfHs
0u+KzJ6MALtonHQOkAbhDTw8zTC+OTHEuN/t2+dwli6E8r7F61RIMpLyPiZpfS0y
rQjHMqJPMdr7Xerhn1haGdov2MzbvtloqHBEP9T65fstTEYBXoYMDSNhYVRV1Fpz
g+is39fVr6D3LZ5W50VQhtTwmcpGM7ZKl4XSgqtv2UwwPM7dYjMQ+Qgz+5MnPLe3
wZlD06/bvrbY5InFRQFMaFhNtVAC6v42G6W8AOv8WD0kXJCopUGOwYelQ40qhdug
DvXWxpApv7jgmStms63AlG3TjQemwF3rkreFsk9IClAZ5T3EpTafqVd3HC4oYBc=
=OqFT
-----END PGP SIGNATURE-----