brute force physics Was: cleversafe...

[Florian Weimer]

* 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                <fweimer at bfk.de>
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 majordomo at metzdowd.com