0
$\begingroup$

I am wondering whether there are any results/whether there is any knowledge about the following problem:

Given a univariate polynomial (say, a quartic) equation defined over $\mathbb{Z}_N$, is it possible to find its roots/factorisation in polynomial time? I know that there exist randomized/average-case polynomial algorithms for doing so over finite fields $\mathbb{Z}_p$, and given $p$, $q$, where $N = pq$, one can reduce the problem to finding roots in $\mathbb{Z}_p$ and $\mathbb{Z}_q$ with the Chinese Remainder Theorem, but I am interested in the situation where the factorisation of $N$ is not known for cryptographic applications where $N$ is a RSA modulus.

Considering the case of the quartic equation, the closed solution requires computing square roots modulo $N$, which is as difficult as factoring $N$, but I am wondering if there may be a different way to do so in this case that bypasses this need (and is polynomial).

Indeed, halving a point over an elliptic curve reduces to solving such a quartic equation, which motivates my question. Perhaps there is a way to halve points over $\mathbb{Z}_N$ without needing to do this? I am not sure. This is my main concern, because it would seem like solving a general quartic reduces directly to the quadratic residuosity problem, but the group law gives you a quite specific quartic equation.

Thanks in advance!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.