Math question - factoring a bivariate polynomial

[Max A.]

Andrew,

What you really need is the factorization of

D = b^2 + 2ab + 4c

Note that

0= 4*(x^2 - ax - 2xy - by + c)
= (2x - 2y - a)^2 - (2y + a + b)^2 + D

Then
(2y + a + b)^2 - (2x - 2y - a)^2 = D
implying that
(2x + b) * (4y - 2x + 2a + b) = D

If you know the factorization of D, you can go over all
representations of D as the product of two factors, say, D=z*t, and
for each such representation solve the system of linear equations
2x + b = z
4y - 2x + 2a + b = t
to obtain
x = (z-b)/2
y = (z + t - 2a - 2b)/4

Max

On 10/18/06, Andrew Plewe <aplewe at sbcglobal.net> wrote:
> I have a question related to an algorithm and several sequences I'm working
> on. Feel free to answer off-list and only if you have some spare time to do
> so.
>
> Let us assume you have the following polynomial:
>
> a.) x^2 - ax - 2xy - by + c = 0
>
> Assume that a, b, and c are large (>80 digits) composite integers whose
> factorizations are known. I wish to find valid values for x and y. Is it
> easier to factor the polynomial directly, or to find solutions to:
>
> b.) x^2 - ax - 2xy + c = 0 modulo b
>
> And then search within those values for x,y which satisfy eqn a?
>
> Thanks for your time!
>
>         -Andrew Plewe-
>
>
>
>