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$

closed as off-topic by Yuval Filmus, Evil, fade2black, David Richerby, Rick Decker Jan 10 '18 at 0:42

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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