Quantum computing
Anders Breindahl
skrewz at skrewz.dk
Wed Apr 18 09:10:17 CEST 2007
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
More information about the Gnupg-users
mailing list