Is it possible to subtract a perfect square from another number to make it a perfect square? A number $c$ is given. We need to find a number $0<k<c$ such that 
$c^2 - k^2$ is a perfect square. (if it is possible)
$c$ and $k$ can be any positive integer.
What I tried is-


*

*I iterated for all the values $[1,c-1]$ and stopped at the first $k$ which satisfies the condition. 

*The Euclid's method to find a Pythagorean triple which takes O(c0.5) run time. We do not actually find a solution. But, we just need to check if it is possible or not. 
Can the solution be better than this? What I am looking for is a more efficient solution. Maybe some algebraic formula or proof.
 A: There is a method based on the observation that according to Euclid's solution, if $c$ is the hypothenuse of an integral right triangle then there are coprime integers, $n$ and $m$ and an integer $t$ such that 
$$ c = t^2(m^2+n^2) $$
So the problem will be solved if we find a way to write an integer $c$ as sum of two squares. The algorithm works as follows: 


*

*Factor $c = t^2p_1p_2\dots p_s$. where the $p_i$ are distinct primes and $t$ is an integer. There will be solutions to the problem if and only if all the $p_i$ are $\equiv 1 \pmod{4}$. This is the most time consuming part but it can be done much faster than $O(\sqrt{c})$ using modern factoring algorithms. 

*For each $p_j$ use Shank's algorithm (or other) to find an square root of $-1 \pmod{p}$. Although Shanks' is a probabilistic algorithm it is very fast. There is an algorithm (Schoof's algorithm) which finds square roots modulo prime in deterministic polynomial time but it is very complicated. 

*Using the result of 2, Use Cornacchia's algorithm to find integers $a_j$ and $b_j$ with 
$$ a_j^2+ b_j^2 = p_j$$
see also the answers to this question

*Use the classical formula for the product of two sums of two squares 
$$ (a^2+b^2) (c^2+d^2) = (ac+bd)^2 + (ad-bc)^2$$
recursively to obtain a solution of $c/t^2 = A^2 + B^2$, then set $k=tA$ and you are done. You can also use complez arithmetic to do this in a simpler but equivalent way:
$$ A + B i = (a_1+ib_1)(a_2+ib_2)\dots(a_s+ib_s) $$
