Is there an algorithm for writing an integer as a difference of squares?

Question

For example, if we have $36$, is there an algorithm to determine that it may equal $10^2-8^2$? What if we blow up the number to something like $492709612098$? Can it be written as the difference of two squares? If so, how do we know?

Also, does it matter if the number in question has more or fewer factors?

EDIT: I WANT TO KNOW THE ALGORITHM, AND NOT WHETHER A NUMBER MAY BE WRITTEN AS SUCH. BASICALLY I WANT TO KNOW IF THERE IS AN ALGORITHM WHERE YOU CAN INPUT NUMBER $N$ AND GET THE ADDEND SQUARE NUMBER $X$.

Answer 1

Let N=ab then consider $a=c+d$ and $b=c-d$. Then $c=\frac{a+b}{2}$ and $d=\frac{a-b}{2}$ now $N=c^2-d^2$. So the only numbers that can't be written as the difference of two squares are of the form $2K$ where K is an odd number. So your number $492709612098$ can't be written as a difference of two squares because $492709612098=2*246354806049$

Here is the algorithm in pseudocode

1) Write the number in the form $n=a*b$ where either $a$ and $b$ are both even or $a$ and $b$ are both odd

2) set $c=\frac{a+b}{2}$ and $d=\frac{a-b}{2}$

3) Now $N=c^2-d^2$

Answer 2

This might answer partially your needs. One option is using Pythagorean triples $(a,b,c)$ of the form $a^2+b^2=c^2$, there is a known formula to obtain those kind of triples. Here is the link to the explanation at the Wikipedia.

If you can generate a triple $(a,b,c)$, then you can obtain $a^2 = c^2-b^2$ or $b^2 = c^2-a^2$.

Indeed if you obtain one primitive Pithagorean triple $(a,b,c)$ such as $a^2+b^2=c^2$ then you got a whole family of Pythagorean triples $ \forall k\gt 1\,\ (ka,kb,kc)\ /$ $(ka)^2 + (kb)^2 = (kc)^2$.