That would be a reasonable question to ask, and it would be easy to give counterexamples showing that it fails (on 4, for example, since 2 > cube_root(4)). It seems just as reasonable to ask about AKS, where many of the bounds in the original paper are not sharp. The easy answer: we don't know that the resulting algorithm would be valid. But can we show that it wouldn't be? :unsure:

[QUOTE=CRGreathouse;263563] But can we show that it wouldn't be? :unsure:[/QUOTE]

exactly that was my point too, except the fact that in my case the example was stupid. for my "algorithm" we still need to "prove" (well, in this case a proof would be quite easy), otherwise we could say that the algorithm remain valid with two exceptions, 323 and 4 :redface:

in real aks algorithm I would read the log2 part as "the number of bits in n" and suddenly all it makes sense why can't be lowered (or say, not too much and not for general case).

p.s. and sorry for the formulation "primes with small factors" in previous post, read it as "numbers with small factors". that was silly too, but you got the point