> "Polynomial?"
>
> I think and please correct if I am wrong that trial factorisation
> using long division requires O(sqrt(n)*log(n)) operations.
> sqrt(n)*log(n) is polynomial in n e.g. it is less than n^2.
> Presumably when measuring the order of factorisation
> algorithms you guys use n ~ e^x and then measure the
> order in terms of x?
Well, it is polynomial to n, but we want it so that the runtime is polynomial
to the digits of n (log(n)), which O(sqrt(n)*log(n)) is exponential to log(n).
-Lucas
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
