Math question - factoring a bivariate polynomial

[Andrew Plewe]

Thanks for your reply. My only issue here is that D gets to be too large to
factor. I think it may be easier to solve the system of bivariate polynomial
congruences:

x^2 - ax - 2xy + c = 0 modulo bf_1
x^2 - ax - 2xy + c = 0 modulo bf_2
.
.
.
x^2 - ax - 2xy + c = 0 modulo bf_n

where {bf1, bf2,...bfn} represent the factors of b. I've been looking at
these lectures online:

http://theory.lcs.mit.edu/~madhu/FT05/ (specifically lectures 8 through 10)

to get and idea of how it could work. I assume I could solve all the
polynomial congruences individually and then look for a composite solution
which satisfies x^2 - ax - 2xy + c = 0 modulo b. But I'm still just starting
to figure out how this all works, so perhaps it's not as easy as I think.

	-Andrew Plewe-

-----Original Message-----
From: Max A. [mailto:maxale at gmail.com]
Sent: Wednesday, October 18, 2006 1:58 PM
To: Andrew Plewe
Cc: seqfan at ext.jussieu.fr
Subject: Re: Math question - factoring a bivariate polynomial

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-
>
>
>
>