On Sat, 2008-09-06 at 06:32 +0000, azogue.2007 wrote:

>

>

> Hello everybody.

>

> Im wondering about the state of the art about the class of compexity

> of the integer factorization problem.

>

> Could anybody comment something about it?.

> Concretely, What is it known about if such problem is pertaining to

> NP-

> complete class?

>

> Thanks in advance for your comments.

>

> Victor M. Castillo-Vallejo

It is trivial to prove that factoring is in NP. (Proof: guess the

factors and use grammar-school multiplication, an O(N) algorithm to

verify that the product of the factors is the number being factored).

It is not yet known whether factoring is in P.

Paul