Let $N$ be composite. It is well-known that if $x^2 \equiv 1 \pmod N$, and $x \neq \pm 1 \pmod N$, then a factor of $N$ is easily found by computing gcd($N$, $x + 1$). I'm curious if there is a similar approach to factor $N$ given $y$ such that $y^2 \equiv 2 \pmod N$. (We are obviously assuming that 2 is a quadratic residue mod $N$).
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ It works if you have two such $y$ which don't sum to $0$. $\endgroup$– WhatsUpCommented Jan 8, 2021 at 6:52
-
$\begingroup$ For a bit more analysis in the case where N is an RSA modulus, see Section 4 of Rabin's "Digitalized Signatures and Public Key Functions as Intractable as Factorization" . $\endgroup$– Ben SmithCommented Jan 8, 2021 at 12:04
Add a comment
|