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

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

Expand Messages
  • Kermit Rose
    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
    Message 1 of 2 , Dec 11, 2007
      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@... >
    • Paul Leyland
      Very, very unlikely to be useful. This approach has been made many times in the last few centuries (entirely analogous equations can be set up in any radix,
      Message 2 of 2 , Dec 13, 2007
        Very, very unlikely to be useful.

        This approach has been made many times in the last few centuries
        (entirely analogous equations can be set up in any radix, including 10)
        and everyone has run into the (apparently) insurmountable obstacle that
        the solution of the equations blows up exponentially and, in particular,
        take much longer even than trial division.


        Paul


        On Wed, 2007-12-12 at 03:33, Kermit Rose wrote:
        >
        > 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@... >
        >
        >
        >
        >
        >


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