View Single Post
Old 2015-01-02, 06:29   #1
axn
 
axn's Avatar
 
Jun 2003

17·281 Posts
Default 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^((p-1)/3) == 1, but is there a faster method?

Alternatively, how can I efficiently find a cubic non residue (mod p) without searching?
axn is offline   Reply With Quote