* 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önhage, 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. -- Florian Weimer <[email protected]> BFK edv-consulting GmbH http://www.bfk.de/ Kriegsstraße 100 tel: +49-721-96201-1 D-76133 Karlsruhe fax: +49-721-96201-99 --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [email protected]
