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

19156might be or might not be a start in building a new theory of factoring

Expand Messages
  • Kermit Rose
    Dec 11, 2007
    • 0 Attachment
      Suppose that z is a composite odd integer for which we wish to know factors

      z = x y.

      Set x = 2^0 + 2^c2 + 2^c3 + . . . + 2^cm

      Notice that the subscripts begin with 2.

      The exponents are from the usual base 2 representation of x.


      Set y = 2^0 + 2^d2 + 2^d3 + . . . + 2^dn


      Notice that the subscripts begin with 2.

      The exponents are from the usual base 2 representation of y.

      Set p(r) to be the polynomial

      p(r) = 1 + r^c2 + r^c3 + r^c4 + . . . + r^cm


      Notice that p(2) = x and p(1) = m.


      Set q(r) to be the polynomial

      q(r) = 1 + r^d2 + r^d3 + . . . + r^dn


      Notice that q(2) = y and q(1) = n.


      Set u(r) = p(r) * q(r).

      Notice that u(2) = z and u(1) = m * n

      Let v0,v1, v2, ... vf be the coefficients of u.

      u(r) = v0 + v1 r + v2 r^2 + v3 r^3 + . . . + vf r^f.

      Notice that

      v0 = 1 since z, x, and y are odd.


      Define

      s0 = m

      s1 = c2 + c3 + . . . + cm

      s2 = c2^2 + c3^2 + . . . + cm^2

      etc.

      In general, for each positive integer k,

      define

      sk = c2^k + c3^k + c4^k + . . . + cm^k


      Define

      t0 = n

      t1 = d2 + d3 + d4 + . . . dn

      t2 = d2^2 + d3^2 + . . . + dn^2

      etc

      In general, for each positive integer k,


      define

      tk = d2^k + d3^k + d4^k + . . . + dn^k

      Notice that if we had defined d1 = 0, and took the convention that 0^0 = 1,

      then

      t0 would have been equal to d1^0 + d2^0 + d3^0 + . . . + dn^0.


      I saw that the following equations could be set up.


      v0 + v1 + v2 + . . . + vf = s0 t0

      v1 + 2 v2 + 3 v3 + . . . + f vf = s0 t1 + s1 t0

      v1 + 4 v2 + 9 v3 + . . . + f^2 vf = s0 t2 + 2 s1 t1 + s2 t0

      v1 + 8 v2 + 27 v3 + . . . + f^3 vf = s0 t3 + 3 s1 t2 + 3 s2 t1 + s3 t0

      etc

      These equations could (theoretically ) be solved to express the
      coefficients
      v0,v1,v2, . . . vf in terms of

      s0, s1, s2, .....
      and
      t0, t1,t2, . . .


      I have hope that such a solution would be helpful in figuring out the
      coefficients

      of
      x = 1 + 2^c2 + 2^c3 + . . . + 2^cm

      and

      y = 1 + 2^d2 + 2^d3 + . . . + 2^dn.

      We also have the following equations from

      u(r) = p(r) * q(r)


      Define a0,a1,a2,. . .,a_cm

      by p(r) = a0 + a1 r + a2 r^2 + a3 r^3 . . . + a_cm r^cm

      Note that a0, a1, . . . a_cm are exactly the bit values in the usual
      base 2 representation of x.

      Similarly, define

      b0,b1,b2, ...., b_dn

      by q(r) = b0 + b1 r + b2 r^2 + . . . + b_dn r^dn.

      Notice that b0, b1, b2, are exactly the bits of the usual base 2
      representation
      of y.


      v0 = a0 * b0

      v1 = a0 b1 + a1 b0

      v2 = a0 b2 + a1 b1 + a2 b0

      v3 = a0 b3 + a1 b2 + a2 b1 + a3 b0

      etc



      I've also explored ways to set up equations relating
      the

      v0, v1, v2, .....
      a0, a1, a2, .....
      b0, b1, b2, . . .

      z0, z1, z2, . . .

      where the z0, z1, z2, . . . come from the base 2 representation of z.

      z = z0 + 2 z1 + 4 z2 + 8 z3 + . . .



      Kermit Rose < kermit@... >
    • Show all 2 messages in this topic