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.

The same is true for your problem.

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.

  • $\begingroup$ Thank you. I understood the first approach (second I have to think about more), but I am unclear about this: "This will be efficient if there aren't too many square roots, i.e., if N doesn't have too many different prime factors." Why would it be difficult if there are too many different prime factors? Aren't we just repeating the same process the second time ? $\endgroup$
    – J.Doe
    Mar 23 '18 at 16:28
  • $\begingroup$ @J.Doe, en.wikipedia.org/wiki/…. I suggest spending some quality time with a number theory textbook. $\endgroup$
    – D.W.
    Mar 23 '18 at 16:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.