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!


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.