Re: Mersenne: Re: Meganet Corp.

[Daniel Grace]

> 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. > > Jud McCranie wrote : > It means that it is a polynomial function of the number of bits in > n. ... or nibbles, bytes or whatever base your machine is working in ... basically whatever you consider as requiring O(1) operations - it does not effect the "O" analysis. > Trial factorization isn't polynomial in the number bits of the number. I did not say it was. Daniel.