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]