1
$\begingroup$

Let $N$ be a composite integer, and suppose we are given a randomly generated solution $(x, y)$ of the equation $x^2 + y^2 \equiv 0 \pmod{N}$. By randomly generated, I mean that $(x, y)$ is selected uniformly at random from the set of all possible solutions. Can we use $(x, y)$ to find a nontrivial divisor of $N$ with high probability?

Note that it is trivial to use a randomly generated solution of the equation $x^2 - y^2 \equiv 0 \pmod{N}$ to factor $N$, since then $(x-y)(x+y) \equiv 0 \pmod{N}$ and there is a 50% probability that the pair $x-y, x+y$ splits $N$.

It is also worth mentioning that only some choices of $N$ admit nontrivial solutions to the equation $x^2 + y^2 \equiv 0 \pmod{N}$; it is precisely those $N$ with the property that every prime $p$ such that $p \equiv 3 \pmod{4}$ appears in the factorization of $N$ with even multiplicity, as shown by Fermat.

Improve this question
$\endgroup$
7
  • 7
    $\begingroup$ A single random solution, no. But if you keep drawing randomly from the set of solutions then you'll soon get two solutions $(x,y), (x',y')$ that are not equivalent up to scaling (i.e. can't be obtained from each other by changing signs or multiplying by a constant), and then $\gcd(N, xy'\pm x'y)$ gives nontrivial divisors. $\endgroup$
    – Noam D. Elkies
    Commented Aug 15, 2021 at 20:04
  • 1
    $\begingroup$ Why is there a 50% probability that $x - y$, $x + y$ splits $N$ if $x^2 - y^2 \equiv 0 \pmod N$? $\endgroup$
    – LSpice
    Commented Aug 15, 2021 at 20:21
  • 2
    $\begingroup$ Note, Gautam, that knowing an expression of $2^{2^n}+1$ as $x^2+y^2$ doesn't seem to help much in factoring Fermat numbers. $\endgroup$
    – Gerry Myerson
    Commented Aug 16, 2021 at 3:04
  • 2
    $\begingroup$ @LSp, the only solution that doesn't yield a factorization is the one with $x-y=1$, $x+y=N$. Given any other solution (with $0<y<x<N$), $\gcd(x-y,N)$ will yield a nontrivial factor of $N$. Maybe the problem arises from my failure to make explicit my assumption that $x$ and $y$ are reduced modulo $N$. $\endgroup$
    – Gerry Myerson
    Commented Aug 16, 2021 at 3:40
  • 1
    $\begingroup$ @GerryMyerson, ah, thanks. I took "$x - y$, $x + y$ splits $N$" to mean that it was a factorisation, rather than just that $\gcd(x - y, N) \ne 1$, but your interpretation makes more sense. $\endgroup$
    – LSpice
    Commented Aug 16, 2021 at 21:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .