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?


1. *Weak form.* Given $N$, $k$, and a factoring oracle, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.
2. *Semi-weak form.* Given $N$, $k$, and the complete factorization of $N$, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.
3. *Strong form.* Given $N$, $k$, and a partial factorization of $N$, find $k$ distinct nontrivial congruences $a^2\equiv b^2\pmod N$.



Differences of squares
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$. 


