If a number N (other than an odd multiple of 2) is the product of two factors, then N = x2 – y2 , where x and y are half the sum and half the difference respectively of the factors, and are integers. To determine x and y we may use the quadratic residues of small primes as follows.

Let N = a 2 + b where a 2 is the perfect square nearest to N.