Mersenne: Re: Meganet Corp.

[Daniel Grace]

"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?   What is a lower bound on a deterministic factoring algorithm?   Puzzled :o   ---------------------------------------------------------- Daniel e-mail: [EMAIL PROTECTED]