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

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