>I think that a polynomial time algorithm means that the algorithm's running
>time is a polynomial in
> Log(n)/Log(2), not n, because the size of the input matters, not the value
>of the number.
That makes sense. You could have said polynomial in log(n) I suppose.
I guess it is in that sense that it is said that PRIMES has been proved
being in P with Riemann hypothesis(*). And that a polynomial probabilistic
algorithm has been find (Solovay and Strassen (**)).