1
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\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
    Commented Sep 1, 2016 at 22:14
  • $\begingroup$ Is there a particular reason why? e.g. would it imply we could factor out $n$? $\endgroup$
    – Ethan Splaver
    Commented Sep 1, 2016 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
    Commented Sep 1, 2016 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 Splaver
    Commented Sep 1, 2016 at 22:51
  • $\begingroup$ See my answer at mathoverflow.net/questions/142938/… $\endgroup$
    – Gerry Myerson
    Commented Sep 1, 2016 at 23:00

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .