It depends on how you measure n. The O(log^{6+\epsilon}(n)) quote on Wikipedia is for n being the number to be tested. This is "cheating"; inputs to an algorith

It depends on how you measure n. The O(log^{6+\epsilon}(n)) quote on Wikipedia is for n being the number to be tested. This is "cheating"; inputs to an algorithm need to be measured by their length, and numbers are exponential in their length (i.e., the length of the number n is order log n for "reasonable encodings"). As an example, the knapsack problem with n objects and weight W is solvable in O(n*W) time, but it's known to be NP-hard. This doesn't prove P=NP, because W is exponential in its length. This is called a pseudopolynomial algorithm.