Question

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$.

Answer 1

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$.

Answer 2

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$.

Answer 3

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.$$