1
$\begingroup$

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

$\endgroup$
1

3 Answers 3

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You've answered my question perfectly, but this makes me realize that there's more I wanted to know. Rather than drag it out here by editing my question, I'll accept your answer and ask a follow-up question. Thanks! $\endgroup$
    – Charles
    Sep 22, 2010 at 0:21
6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.