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

Re: {Spam?} [PrimeNumbers] Question about the class of complexity of integer factorization

Expand Messages
  • 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 1 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.