On Cubic Non-Residues Modulo a Prime 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$?
 A: I am a bit confused by the connection between the first question and the numbered questions. Presumably if $R\equiv 2 \mod 3,$ then everything is a cubic residue, while if $R\equiv 1 \mod 3,$ then $x$ is a residue iff $x^{(R-1)/3} \equiv 1 \mod R.$ This test is quite efficient. I assume (but haven't bothered to check) that this test will answer the numbered questions.
A: 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$.
