Monday, September 14, 2009


JSH: Factoring with general solution?

One of the things I've noted is that last year I derived a general solution for binary quadratic Diophantine equations using what I call tautological spaces. I've been talking about it on the sci.physics newsgroup because such a solution has relevance to quantum mechanics where such equations come up.

But some sci.math'ers have come over and hijacked the discussion and the focus has shifted to factoring, as yes, a general solution to binary quadratic Diophantine equations must also handle factoring because xy= T is a binary quadratic Diophantine, which I didn't even think of with these equation until the poster Enrico brought it up.

But that's not something that interests physics people, so I want a thread here on sci.math for THAT discussion and sci.math'ers can quit bugging me about it on the sci.physics newsgroup.

The general solution that I found allows you to take any binary quadratic Diophantine of the form

c_1*x^2 + c_2*xy + c_3*y^2 = c_4 + c_5*x + c_6*y

and relate solving it to instead resolving u^2 + Dv^2 = F, which is related to prior art, that is, the ways people solve such equations anyway before my research, but my method allows you to do that in one step, across the board for all such equations (with one exception easily handled).

That is not in debate.

What is debated is getting the solution after, where the math I've given turns to an easy relation that follows from the research but is easily verified without it:

Given: x^2 + Dy^2 = F,

(x-Dy)^2 + D(x+y)^2 = F(D+1)

which is why it's a lift, as you repeat using that identity you get a higher power of D+1, for instance, next is:

((1-D)x-2Dy)^2 + D(2x + (1-D)y)^2 = F(D+1)^2

so you can solve for u and v, with

u^2 + Dv^2 = F(D+1)^j

where j is arbitrarily high and step back down the chain to your original equation.

THAT is the second piece and it's important to note that the general solution I've found is VERY easy and has two parts:
  1. It allows you to get to the form u^2 + Dv^2 = F, to solve any binary quadratic Diophantine of the form:

    c_1*x^2 + c_2*xy + c_3*y^2 = c_4 + c_5*x + c_6*y

  2. A simple relation that follows from the method gives you

    u^2 + Dv^2 = F(D+1)^j

    where j can be arbitrarily high and any solution to it can be used to get a solution to the original equation by stepping down the chain (there are j steps I think).
Now then to try to use this to factor you need:

x^2 - k^2*y^2 = T

where T is the target and that also just gives a difference of squares, and (x-ky)(x+ky) = T, so it's easy to see WHY it factors if you get solutions.

My approach then would require solving

u^2 - k^2*v^2 = T(1 - k^2)^j

where you need to pick k, where I'd guess it'd need to be large, maybe approximately sqrt(T), and then you'd use:

u^2 = k^2*v^2 mod T(1-k^2)^j


u^2 = T(1-k^2)^j mod k^2*v^2

where I say just guess at v, like assume v = 1, use the Chinese Remainder Theorem to get

u^2 mod k^2*T(1-k^2)^j

and if u^2 mod k^2*T(1-k^2)^j is a perfect square you have a solution.

Notice you may get fractions with this approach (probably will get fractions) which STILL may factor T in the original equation.

In any event THAT is the full approach for people who wish to criticize it, and you don't need to post to sci.physics about factoring!!!

An immediate criticism is guessing at the residue of v. If that never works, ok, prove it. If you say I haven't proven it works, fine.

But that I think covers all the territory. If it does work and with large j you tend to get a perfect square, with a guessed at residue for v, then that should allow solution.

<< Home

This page is powered by Blogger. Isn't yours?