Differences of squares Suppose I wanted to express a number $N$ as a difference of squares. For large $N$ this is in general difficult, as finding $N=a^2-b^2$ leads to the factorization $N=(a+b)(a-b)$. Even if the problem is weakened to searching for $a\neq b$ with $a^2\equiv b^2\pmod N$ the problem is still hard (though not as hard), since enough congruences could be used to factor $N$ with Dixon's method or any of its modern versions (in particular, the number field sieve).
So I am curious about the difficulty of these weak versions of the problem.  Are any of these easier than finding relations with the NFS?


*

*Weak form. Given $N$, $k$, and a factoring oracle, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.

*Semi-weak form. Given $N$, $k$, and the complete factorization of $N$, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.

*Strong form. Given $N$, $k$, and a partial factorization of $N$, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.
 A: Here is a simple way to find one representation of $N$ as a difference of two squares.
No integer $N\equiv 2 \text{ mod } 4$ is a difference of squares.
If $N$ is odd, then
$$ N= (\frac{N+1}{2})^2 - (\frac{N-1}{2})^2.$$ 
If $4|N$, then
$$ N=(\frac{N}{4}+1)^2 - (\frac{N}{4}-1)^2.$$
A: I think he is more interested in how many ways can one number be written as a difference of squares.
The solution to the semiweak form is actually simple, since $a+b$ and $a-b$ have the same parity.
If $N$ is odd, then as long as $N$ has at least 2k divisors (which can easely be seen from the factorisation of $N$) you can simply write $k$ different pairs $(d,N/d)$ with $d$ smaller than $N/d$ and solve 
$$a-b= d \,;\, a+b= N/d \,.$$
If $N\equiv 2 \text{mod} 4$ there is no solution as noted above.
If $N\equiv 0 \text{mod} 4$ then you do the same trick for $N/4$:  as long as $N/4$ has at least 2k divisors  you can simply write $k$ different pairs $(d,N/4d)$ with $d$ smaller than $N/4d$ and solve 
$$a-b= 2d \,;\, a+b= N/2d \,.$$
Edit: Same thing works for the strong form, as long as the partial factorisation of $N$ is "big" enough: i.e. it allows us to find k distinct pairs pairs $(d,N/d)$ of divisors of same parity with $d$ smaller than $N/d$. 
A: If you know any factors of $N$, it's easy to find non-trivial solutions of $a^2\equiv b^2\pmod N$. If $m$ and $n$ are (relatively prime) factors of $N$, then given any $a$, take $b$ to solve $b\equiv a\pmod m$, $b\equiv-a\pmod n$. 
EDIT: A bit careless of me, let's try again. If $N$ is odd and $N=mn$ is non-trivial with $\gcd(m,n)=1$, then the construction above, with $\gcd(a,N)=1$, gives a non-trivial solution of $a^2\equiv b^2\pmod N$. 
