Quantum computing

[Anders Breindahl]

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:

  http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity:
  the best published asymptotic running time is for the general number
  field sieve (GNFS) algorithm, which, for a b-bit number n, is:
  O(exp(64/9b)^(1/3)(log b)^(2/3))

But for quantum computers, it'd seem that Shor's algorithm provides a
leap:

  http://en.wikipedia.org/wiki/Shor's_algorithm:
  Shor's algorithm is a quantum algorithm for factoring a number N in
  O((log N)^3) time and O(log N) space.

However, since large quantum computers are rather expensive, getting log
N space is so costly that it isn't relevant just yet.

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.

By the way, I realize that this is a more general question of gnupg's
life expectancy in a quantum computer world. But it's interesting to get
answered.

Regards, skrewz.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : /pipermail/attachments/20070418/e9041b5f/attachment.pgp