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

Maybe progress in applying algebraic factoring to integer factoring

Expand Messages
  • Kermit Rose
    The following might or might not be progress in factoring theory. We seek the factors of z = r^4 + d3 r^3 + d2 r^2 + d1 r + d0, where d3,d2,d1,d0 are not
    Message 1 of 1 , Apr 13 6:50 AM
    View Source
    • 0 Attachment
      The following might or might not be progress in factoring theory.

      We seek the factors of z = r^4 + d3 r^3 + d2 r^2 + d1 r + d0,
      where d3,d2,d1,d0 are not necessarily between 0 and (r-1), inclusively.

      Suppose the factors are of the form

      (r^2 + a1 r + a0) ( r^2 + b1 r + b0) = r^4 + d3 r^3 + d2 r^2 + d1 r + d0.


      (r^2 + a1 r + a0) ( r^2 + b1 r + b0) = r^4 + (a1+b1) r^3 + (a1 b1 + a0
      +b0) r^2 + (a0 b1 + b0 a1) r + a0 b0


      It is not valid to equate coefficients of powers of r directly.

      However, we can introduce parameters t1, t2, t3 such that

      a1 + b1 = d3 - t3

      a1 b1 + a0 + b0 = d2 - t2 + t3 r

      a0 b1 + b0 a1 = d1 - t1 + t2 r

      a0 b0 = d0 + t1 r

      I've noticed that

      (d3 - t3) + (d2 - t2 + t3 r) + (d1 - t1 + t2 r) + (d0 + t1 r) + 1

      = (d3 + d2 + d1 + d0) + (r-1) (t1 + t2 + t3) + 1

      = a1 + b1 + a1 b1 + a0 + b0 + a0 b1 + b0 a1 + a0 b0 + 1

      = a1 b1 + a0 b1 + b0 a1 + a0 b0 + a1 + a0 + b1 + b0 + 1

      = (a1 + a0)(b1 + b0) + (a1 + a0) + (b1 + b0) + 1

      = (a1 + a0 + 1) (b1 + b0 + 1)

      We pull from these equalities the conclusion

      (a1 + a0 + 1) (b1 + b0 + 1) = (d3 + d2 + d1 + d0) + (r-1) (t1 + t2 + t3) +1


      Perhaps we can figure out how to use this constraint on the coefficients

      to solve the equation

      (r^2 + a1 r + a0) ( r^2 + b1 r + b0) = r^4 + d3 r^3 + d2 r^2 + d1 r + d0.

      for a1, a0, b1, b0, t1, t2, t3.


      Kermit Rose
    Your message has been successfully submitted and would be delivered to recipients shortly.