Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Continuation: mathoverflow.net/questions/39567/… –  Charles Sep 22 '10 at 1:12

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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! –  Charles Sep 22 '10 at 0:21

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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