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

Polynomial remainder?

Expand Messages
  • Ron
    I m puzzled. Symbolic polynomial division (with remainder) can easily be shown to be the same level of difficulty as factoring, but descriptions of the
    Message 1 of 2 , Feb 1, 2005
    • 0 Attachment
      I'm puzzled.

      Symbolic polynomial division (with remainder) can easily be shown to
      be the same level of difficulty as factoring, but descriptions of the
      algorithm such as that shown at
      http://mathworld.wolfram.com/LongDivision.html appear to be of about
      the same level of difficulty as multiplication!? Obviously it can't
      be both.

      Where am I going wrong?

      -- Ron
    • Décio Luiz Gazzoni Filho
      ... As factoring polynomials or integers? As far as I know, factoring polynomials is polynomial-time. At least factoring in Z/pZ. By the way, this underscores
      Message 2 of 2 , Feb 1, 2005
      • 0 Attachment
        On Tuesday 01 February 2005 10:54, you wrote:
        > I'm puzzled.
        >
        > Symbolic polynomial division (with remainder) can easily be shown to
        > be the same level of difficulty as factoring,

        As factoring polynomials or integers? As far as I know, factoring polynomials
        is polynomial-time. At least factoring in Z/pZ.

        By the way, this underscores the main problem: what is the underlying field
        that you're doing factoring on? The relative complexity for each operation
        may be different depending on the field.

        Décio


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.