Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It's a bad idea to change the question after it was answered. $\endgroup$– Max AlekseyevCommented Apr 19, 2022 at 16:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Ability to find all roots leads to finding factorization of $N$. For example, if $N=pq$ is a product of two odd primes, and we find a root $x'$ of $x^2-1\equiv 0\pmod N$ such that $x'\equiv 1\pmod p$ and $x'\equiv -1\pmod q$, then we can compute $p$ as $\gcd(N,x'-1)$.
answered Apr 18, 2022 at 18:30
-
$\begingroup$ @MaxAleseyev What if $|a|$ or $|b|$ or $|c|$ is large? $\endgroup$– TurboCommented Apr 18, 2022 at 18:40
-
$\begingroup$ Same idea works for $(x+u)^2-v^2$ where $u,v$ are large integers. $\endgroup$ Commented Apr 18, 2022 at 18:46
-
$\begingroup$ That is correct. Thank you. Is there an example if only $|a|$ is large? $\endgroup$– TurboCommented Apr 18, 2022 at 19:49
-
$\begingroup$ E.g., consider $a^2x^2-1$. $\endgroup$ Commented Apr 18, 2022 at 20:21
-
1$\begingroup$ @Turbo: It's easy to construct polynomial $(a^2\bmod N)x^2-1$ that will be irreducible over $\mathbb Q$. $\endgroup$ Commented Apr 19, 2022 at 16:05