### Wednesday, March 04, 2009

## Dual factorization equations and factoring

The following post steps through the mathematical underpinnings of a remarkably simple factoring method which relies on dual factorizations. It steps off from the familiar Pell's Equation—with rationals—and through basic algebra proves a viable factoring technique.

In rationals starting with Pell's equation:

x^2 - Dy^2 = 1

I have proven that

(D-1)j^2 + (j+/-1)^2 = (x+y)^2

where j = ((x+Dy) -/+1)/D.

Here the +/- indicates that one variation will work so it is an OR and not an AND. Either plus OR minus will give a valid j.

It suffices to substitute out j, and simplify, which will give Pell's Equation again, showing the relations are valid.

Dual factorizations:

The utility of the expressions comes from dual factorizations:

(x-1)(x+1) = Dy^2

gives an opportunity to factor D, which I will declare to be an odd composite.

While

(D-1)j^2 = (x+y - (j+/-1))(x+y + (j+/-1))

gives the opportunity factor D-1.

Focusing on the second factorization, note to generalize I need additional variables.

Introducing u and v, where j = uv, I further need factors f_1 and f_2 where f_1*f_2 = D-1.

Then I have for generality

(x+y - (uv+/-1)) = u*f_1

and

(x+y + (uv+/-1)) = u*v^2*f_2

Note that f_1 and f_2 can be declared to be integers, and further that x and y uniquely determine u and v, as consider:

(x+y + (uv+/-1)) = (uv)*v*f_2

where I remind that j = ((x+Dy) -/+1)/D = uv, so given any x and y in rationals, I can simply separate off all non-unit non-zero integer factors in common with D-1, for f_1 in the first, and for f_2 in the second, leaving u and v as rationals, and trivially solved and proven to exist as rationals.

Therefore, it is proven that for every x and y that fulfill Pell's Equation there is a u and v pair.

Given that there must exist x and y, such that (x-1)(x+1) = Dy^2, non-trivially factors D, it is proven there exists a u and v pair unique to any such cases.

That completes the underlying mathematical proof showing the dual factorization and proving the existence of rational v, for a non-trivial factorization of a composite D.

It is now possible to move further into the utilities of these expressions and reveal a direct factoring method.

There are then three equation available:

(x+y - (uv+/-1) = u*f_1

(x+y + (uv+/-1) = u*v^2*f_2

((x+Dy) -/+1)/D = uv

Considering x and y to be unknowns it follows then that x and y can be determined as functions of v. Doing so gives:

y = [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

and

x = +/-(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v) - [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

Given that y and x are now expressed as functions of v, f_1 and f_2, it is now possible to elucidate a fairly simple factoring method. Said method requires the addition of new functions, so let x = r(v)/t(v), and y = s(v)/t(v), where r(v) is the numerator of the x function, s(v) is the numerator of the y function, and t(v) is the denominator.

Note that t(v) is the easiest given as:

t(v) = f_1 - f_2*v^2 - 2v

Then making the substitutions into the factorization of Pell's Equation: (x-1)(x+1)=Dy^2, and simplifying slightly, I now have

(r(v) - t(v))(r(v) + t(v)) = D(s(v))^2

Note that it suffices if r(v) and t(v) are integers for

abs(r(v) - t(v)) < D and abs(r(v) + t(v)) < D

to guarantee a non-trivial factorization. The absolute values may at first seem problematic, but note that if D is positive then the right side must be positive, forcing the two expressions to match by sign. So it is possible to simply add them, giving the result:

abs(2r(v)) < D

So remarkably, it is proven that rational v must be found such that r (v) is an integer and abs(r(v)) < D/2, and you are guaranteed to non-trivially factor D.

That completes the proof. The factoring problem is then, solved.

Comments or questions are appreciated.

Thank you for your time and attention.

In rationals starting with Pell's equation:

x^2 - Dy^2 = 1

I have proven that

(D-1)j^2 + (j+/-1)^2 = (x+y)^2

where j = ((x+Dy) -/+1)/D.

Here the +/- indicates that one variation will work so it is an OR and not an AND. Either plus OR minus will give a valid j.

It suffices to substitute out j, and simplify, which will give Pell's Equation again, showing the relations are valid.

Dual factorizations:

The utility of the expressions comes from dual factorizations:

(x-1)(x+1) = Dy^2

gives an opportunity to factor D, which I will declare to be an odd composite.

While

(D-1)j^2 = (x+y - (j+/-1))(x+y + (j+/-1))

gives the opportunity factor D-1.

Focusing on the second factorization, note to generalize I need additional variables.

Introducing u and v, where j = uv, I further need factors f_1 and f_2 where f_1*f_2 = D-1.

Then I have for generality

(x+y - (uv+/-1)) = u*f_1

and

(x+y + (uv+/-1)) = u*v^2*f_2

Note that f_1 and f_2 can be declared to be integers, and further that x and y uniquely determine u and v, as consider:

(x+y + (uv+/-1)) = (uv)*v*f_2

where I remind that j = ((x+Dy) -/+1)/D = uv, so given any x and y in rationals, I can simply separate off all non-unit non-zero integer factors in common with D-1, for f_1 in the first, and for f_2 in the second, leaving u and v as rationals, and trivially solved and proven to exist as rationals.

Therefore, it is proven that for every x and y that fulfill Pell's Equation there is a u and v pair.

Given that there must exist x and y, such that (x-1)(x+1) = Dy^2, non-trivially factors D, it is proven there exists a u and v pair unique to any such cases.

That completes the underlying mathematical proof showing the dual factorization and proving the existence of rational v, for a non-trivial factorization of a composite D.

It is now possible to move further into the utilities of these expressions and reveal a direct factoring method.

There are then three equation available:

(x+y - (uv+/-1) = u*f_1

(x+y + (uv+/-1) = u*v^2*f_2

((x+Dy) -/+1)/D = uv

Considering x and y to be unknowns it follows then that x and y can be determined as functions of v. Doing so gives:

y = [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

and

x = +/-(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v) - [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

Given that y and x are now expressed as functions of v, f_1 and f_2, it is now possible to elucidate a fairly simple factoring method. Said method requires the addition of new functions, so let x = r(v)/t(v), and y = s(v)/t(v), where r(v) is the numerator of the x function, s(v) is the numerator of the y function, and t(v) is the denominator.

Note that t(v) is the easiest given as:

t(v) = f_1 - f_2*v^2 - 2v

Then making the substitutions into the factorization of Pell's Equation: (x-1)(x+1)=Dy^2, and simplifying slightly, I now have

(r(v) - t(v))(r(v) + t(v)) = D(s(v))^2

Note that it suffices if r(v) and t(v) are integers for

abs(r(v) - t(v)) < D and abs(r(v) + t(v)) < D

to guarantee a non-trivial factorization. The absolute values may at first seem problematic, but note that if D is positive then the right side must be positive, forcing the two expressions to match by sign. So it is possible to simply add them, giving the result:

abs(2r(v)) < D

So remarkably, it is proven that rational v must be found such that r (v) is an integer and abs(r(v)) < D/2, and you are guaranteed to non-trivially factor D.

That completes the proof. The factoring problem is then, solved.

Comments or questions are appreciated.

Thank you for your time and attention.