- Dec 11, 2007Suppose 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@... > - Next post in topic >>