# Higher Residuocity Problem w.r.t. a composite Modulus

An integer $q$ is called a quadratic residue modulo $N$ if it is congruent to a perfect square modulo $N$; i.e., if there exists an integer $x$ such that: $x^2≡q\ (mod\ n)$.

Otherwise, $q$ is called a quadratic non-residue modulo $N$.

Given that $N$ is a composite number (whose prime factorization is known beforehand) can someone help with the generic higher residuocity problem of the form:

$(x^2-c^2)^k≡q\ (mod\ n)$.

Find $x$ (where $c$ is some random integer value)? $k$ is an even number (say 2).

I think we can solve it using an approach similar to the original QRP, but I am struggling with the exact approach. Can someone please help with an explicit example?

Testing whether $q$ is a quadratic residue modulo $n$ is hard when $N$ is composite: it is as hard as factoring $N$, which is believed to be hard when $N$ is large.
If the factorization of $n$ is known and $k=2$, you can test whether $q$ is a quadratic residue; find all square roots, call it $y$, such that $y^2 \equiv q \pmod n$, then for each such square root $y$, test whether $y + c^2 \bmod n$ is a quadratic residue and find a square root of it, i.e., an $x$ such that $x^2 = y + c^2 \pmod n$, and then you will have a solution to your original problem. This will be efficient if there aren't too many square roots, i.e., if $N$ doesn't have too many different prime factors.
Alternatively, assuming $n$ is squarefree and has known factorization $n=p_1 \cdots p_m$ and assuming $k$ is not too large, you can factor the polynomial $(x^2-c^2)^k-q$ over $\mathbb{Z}/p_i\mathbb{Z}$ (separately for each prime factor $p_i$ of $n$), then if this polynomial has a root modulo every $p_i$, combine solutions via the Chinese remainder theorem.