Efficient computation of cubic residue
Given a prime p = 1 (mod 3) and a small prime q < p, how can I quickly tell if q is a cubic residue (mod p)? I can do it slowly by checking if q^((p1)/3) == 1, but is there a faster method?
Alternatively, how can I efficiently find a cubic non residue (mod p) without searching?
