[144732] in cryptography@c2.net mail archive
Re: brute force physics Was: cleversafe...
daemon@ATHENA.MIT.EDU (Florian Weimer)
Thu Aug 13 08:11:44 2009
To: David Wagner <daw@cs.berkeley.edu>
Cc: cryptography@metzdowd.com
From: Florian Weimer <fweimer@bfk.de>
Date: Thu, 13 Aug 2009 11:41:34 +0000
In-Reply-To: <200908120305.n7C35jSO013877@taverner.cs.berkeley.edu> (David Wagner's message of "Tue\, 11 Aug 2009 20\:05\:45 -0700 \(PDT\)")
* David Wagner:
> (Do note that factoring is not NP-complete.)
It's also possible to factor an n-bit number in O(n^k) integer
additions, substractions, multiplications, divisions and comparisons
to zero, for some smallish fixed value of k (an observations which is
due to Sch=F6nhage, IIRC). So you have to look very closely at your
model of computation. It turns out integer arithmetic isn't the
relevant one. Until scalable quantum computers are available, it will
be difficult to forecast what the correct model will be. There might
be practical limits not immediately apparent, similar to our lack of
means to build machine registers which can store integers in the
mathematical sense.
--=20
Florian Weimer <fweimer@bfk.de>
BFK edv-consulting GmbH http://www.bfk.de/
Kriegsstra=DFe 100 tel: +49-721-96201-1
D-76133 Karlsruhe fax: +49-721-96201-99
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
