If $m=p^k$ is a prime power then I know:

$$\exists x\in \mathbb{Z}:x^n\equiv a\bmod p^k\iff a^{\frac{p-1}{\gcd(n,p-1)}}\equiv 1\bmod p^{j}$$ $$\text{ where: }j=\min\left(v_p(n)+1+[p\mid n][p=2],k\right)$$

Thus if I have the prime factorization of $m$ then by the Chinese remainder theorem I can just verify the above congruence holds for every prime power $p^{v_p(m)}$.

However what if I don't know the prime factorization of $m$?

Is there still a simple way to determine if $x^n\equiv a\bmod m$ is solvable?

What about just the special case when $n=2$ i.e. $x^2\equiv a\bmod m$ with $m$ composite?

  • $\begingroup$ I am afraid that even if we know in advance that our $n=4k+1$ is a product of two primes, and $a=-1$, there is no quick way to answer, i.e., to determine whether the primes are congruent to 1 or 3 modulo 4. $\endgroup$ – Fedor Petrov Sep 1 '16 at 22:14
  • $\begingroup$ Is there a particular reason why? e.g. would it imply we could factor out $n$? $\endgroup$ – Ethan Sep 1 '16 at 22:18
  • $\begingroup$ I do not see how this info yields factorisation, but it looks similar. If we would know prime divisors of $m$ modulo respectively small primes, we could apply Chinese theorem. We know bit less: only the values of Legendre symbol. $\endgroup$ – Fedor Petrov Sep 1 '16 at 22:36
  • $\begingroup$ So if $m=pq\equiv 1\bmod 4$ and we know $x^2\equiv -1\bmod pq$ is solvable. Then $\left(\frac{-1}{p}\right)=\left(\frac{-1}{q}\right)=1$, which means that $p\equiv q\equiv 1\bmod 4$. Though how is this significant enough to disallow the possibility a simple method exists? We already knew that either $p\equiv q\equiv 1\bmod 4$ or $p\equiv q\equiv 3\bmod 4$ since $m\equiv 1\bmod 4$. I mean I do suspect you are right as obtaining this much information about the prime factorization of $m$ seems non trivial, but I want to be sure. $\endgroup$ – Ethan Sep 1 '16 at 22:51
  • $\begingroup$ See my answer at mathoverflow.net/questions/142938/… $\endgroup$ – Gerry Myerson Sep 1 '16 at 23:00

The Goldwasser-Micali probabilistic cryptosystem is based on exactly this principle. Let $N=pq$ and let $a$ be an integer with $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)=-1$, i.e., $a$ is a non-residue mod $p$ and mod $q$. The numbers $N$ and $a$ are public knowledge. In order to encrypt a single bit $\beta$, choose a random number $r$ and send $c=r^2\bmod{N}$ if $\beta=0$ and $c=ar^2\bmod{N}$ if $\beta=1$. It seems to be a hard problem to determine $\beta$ unless you know how to factor $N$, but if you do know $p$ or $q$, then it's easy, just compute $\left(\frac{c}{p}\right)$. According to Wikipedia, G-M is "the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions." See https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem for further details.


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.