Newsgroups: sci.math
From: haoyuep@aol.com (Dan Hoey)
Date: 15 Jun 2002 17:33:38 GMT
Subject: Re: Quickly find when it gives a Square

Mike writes:
> Many thanks to all those that replied.. but factoring would cost me
> more than I would save.

I don't think so.  Finding a solution to your problem _is_ factoring,
in its essence.  You can factor by trial division (as you have done),
or you can factor by trial division with some modular constraints
(as in Oscar Lanzi's suggestion) or you can use other methods for
factoring. But you might as well realize you are factoring, so you can
use some of the extensive information available about how to factor
your number in the best way you can, and--conceivably if not likely--
apply the insights of your problem to get new results in some
important mathematics.

Your problem is to find, given integers  a  and  b , a solution in
integers to

  y^2 = x^2 + ax + b .

Modify this to

  a^2 - 4b  =  4x^2 + 4ax + a^2 - 4y^2
            =  (2x+a)^2 - (2y)^2
            =  (2x+a+2y) (2x+a-2y) .

So  (2x+a+2y)(2x+a-2y)  must be a factorization of  a^2-4b.
We can write  a^2-4b = m(m+n), so

  2x+a+2y = m+n
  2x+a-2y = m , which yields

  x = (2m+n-2a)/4
  y = n/4 .

This shows us that we need a factorization where
  n == 0 (mod 4)  and
  m == a (mod 2) .

For instance, when  a=200, b=-147, we must factor  40588  as the
product of two numbers, both even, differing by a multiple of four.

The positive possibilities are

  factorization     m      n       x     y
  2 . 20294         2  20292    4974  5073
  146 . 278       146    132       6    33

Note that from  x  and  y  we can immediately recover the factors  m
and  m+n.  So any method of solving your problem is effectively a
method of factoring  a^2-4b.

Dan Hoey
haoyuep@aol.com