Loading ...
Sorry, an error occurred while loading the content.

Question about the class of complexity of integer factorization

Expand Messages
  • azogue.2007
    Hello everybody. Im wondering about the state of the art about the class of compexity of the integer factorization problem. Could anybody comment something
    Message 1 of 2 , Sep 5, 2008
    • 0 Attachment
      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
    • Paul Leyland
      ... 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
      Message 2 of 2 , Sep 7, 2008
      • 0 Attachment
        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
      Your message has been successfully submitted and would be delivered to recipients shortly.