At 10:30 AM 11/5/99 +0000, Daniel Grace wrote:
> > Trial factorization isn't polynomial in the number bits of the number.
>
>I did not say it was.
You said:
> > At 12:33 AM 11/5/99 +0000, Daniel Grace wrote:
> > >"Polynomial?"
> > >
> > >I think and please correct if I am wrong that trial factorisation
> > >using long division requires O(sqrt(n)*log(n)) operations.
But that is not what we call a "polynomial time" algorithm. Poly time
refers to a polynomial function of the size of the input (bits, digits,
etc) - NOT the size of the number itself.
+---------------------------------------------------------+
| Jud McCranie |
| |
| Programming Achieved with Structure, Clarity, And Logic |
+---------------------------------------------------------+
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
