What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity?


Given $M$ and $N$, is there a good way to find a prime $R$ such that $M$ is cubic non-residue modulo $R$ and $N$ is cubic residue modulo $R$?


Update after David Speyer's answer: Does the probability estimate hold good if $R$ is restricted to be between $M$ and $N$ and $M < 2N$ or $N < 2M$?



On Cubic Non-Residues Modulo a Prime
Assuming that $M$, $N$, $M N$ and $M N^2$ are noncubes, for a random prime $p$, the probability that $p \equiv 1 \bmod 3$ and $M$ is a cube mod $p$ and $N$ is not a cube is $1/9$. Trying some random primes and checking as Igor Rivin describes is probably faster than trying to be clever.


Proof of the probability claim: The hypotheses imply that the splitting field of $\mathbb{Q}(\sqrt[3]{M}, \sqrt[3]{N})$ has Galois group $\mathbb{Z}/2 \ltimes (\mathbb{Z}/3)^2$. Here, writing $\zeta$ for a primitive cube root of unity, this group acts by
$$\pm 1 \ltimes (a,b) \ : \ (\zeta, \sqrt[3]{M}, \sqrt[3]{N}) \mapsto (\zeta^{\pm 1}, \zeta^a \sqrt[3]{M}, \zeta^b \sqrt[3]{N}).$$


Let $\epsilon\_p \ltimes (a\_p,b\_p)$ be the (conjugacy class of) the frobenius at $p$. Then $p \equiv 1 \bmod 3$ if and only if $\epsilon\_p=1$; the numbers $M$ and $N$ are a cubic residue and non-residue respectively if and only if $a\_p=0$ and $b\_p \neq 0$. By the Cebatarov density theorem, we see that the proportion of primes which obey these properties is $2/18 = 1/9$.


