> We can increase the bound and the test remains polynomial, for example

Wrong. That'd not be polynomial anymore. x^x > 2^x = a lot worse than

> try to Log [n] ^Log [n] instead of Log[n]^2

exponentail. Or, if you prefer it in your original language,

Log[n]^Log[n] = 2^Log[n]*(Log[Log[n]]) = n^Log[Log[n]] = much worse than

trial factoring :-)

Peter

[Non-text portions of this message have been removed]