1
$\begingroup$

After coming across the assertion that given

$$ x^2 = y^2 \pmod n \\ x \neq \pm y \pmod n $$

we can then conclude that n factors into

$$ n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y). $$

in this article, I attempted my own example but it doesn't seem to work. I think there's a missing hypothesis, but more importantly, I'm interested in understanding why this would work under the correct conditions.


First, the example given was

$$ \begin{align*} &6^2 = 1^2 \pmod {35} \\ &x+y = 7 \\ &x-y = 5 \end{align*} $$

So applying the gcd with $35$ simply retains the values, yielding the correct factorization

$$35 = 7 \times 5.$$


However, my test example was

$$ \begin{align*} &8^2 = 4^2 \pmod {24} \\ &x+y = 12 \\ &x-y = 4 \end{align*} $$ If we just blindly applied the stated result, we would get

$$24 = 12 \times 4.$$

I would guess the problem is that my selected factors are not coprime. Does anyone have any intuition for why this method works (when it works) or any hints towards a proof?


After some brief pondering, I've noticed it certainly works if the values $x+y$ and $x-y$ are coprime. Their product divides $n$ yet they contain no overlapping factors, so by collecting the factors of $x+y$ and $x-y$ which are also factors of $n$, we will end up with precisely all the factors of $n$ and nothing extra.

$\endgroup$
  • $\begingroup$ Where did you come across that assertion? $\endgroup$ – D.W. Dec 6 '17 at 5:04
  • $\begingroup$ In the linked wikipedia article a few lines into my post $\endgroup$ – Apollys supports Monica Dec 6 '17 at 9:09
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it is a question on elementary number theory not having much to do with computer science per se. $\endgroup$ – Yuval Filmus Jan 5 '18 at 11:00
1
$\begingroup$

The assertion is not correct in general, as you have discovered.

However, here is what is correct: $\gcd(x+y,n)$ is a factor of $n$, and $\gcd(x-y,n)$ is a factor of $n$. Why? Well, this is trivial: $\gcd(\text{anything},n)$ is always a factor of $n$. Of course, the gcd might be 1, but that's still a divisor of $n$.

We can say even more. If we let $r=\gcd(x+y,n)$ and $s=\gcd(x-y,n)$, then their product is a multiple of $n$: i.e., $rs$ is a multiple of $n$. Thus, you can replace $s$ with $s'=n/r$ and now $r,s'$ will have the property you want: both $r$ and $s'$ are divisors of $n$, and $rs'=n$. (Why is $rs$ a multiple of $n$? Because if $x^2 \equiv y^2 \pmod n$, then it follows that $x^2 - y^2 \equiv 0 \pmod n$. Now $x^2-y^2 = (x-y)(x+y)$, so it follows that $n$ divides $(x-y)(x+y)$, i.e., $n$ divides $rs$.)

This makes this method useful for factoring. However, beware that there is no guarantee that get a non-trivial factor out of this. For instance, consider $n=15$. Then if $x=8$ and $y=7$, we have $x^2 \equiv y^2 \equiv 4 \pmod n$, but $\gcd(x-y,n)=1 $ and $\gcd(x+y,n)=15$, so we obtain that $15 = 1 \times 15$ -- true, but not very useful for factoring $n$. What we can say is that if $n$ is the product of two large primes, and if you can randomly sample two $x,y$ such that $x^2 \equiv y^2 \pmod n$, then with probability about $1/2$, $\gcd(x-y,n)$ and $\gcd(x+y,n)$ will give you the full factorization of $n$.

If you want us to comment on an assertion it helps to give a reference for it. My guess would be that there is additional context you are not providing, such as the assumption that $n$ is a product of two primes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "My guess would be that there is additional context you are not providing, such as ..." -> No, I linked the wikipedia article, so that's the full context... $\endgroup$ – Apollys supports Monica Dec 6 '17 at 9:08
  • $\begingroup$ @Apollys, The Wikipedia article doesn't make the assertion that you said you came across. The Wikipedia article never says that $n$ factors into $\gcd(n,x-y) \times \gcd(n,x+y)$. What it does say is that $n$ divides that product... not that $n$ is equal to that product. $\endgroup$ – D.W. Dec 6 '17 at 15:47

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