20150102, 06:29  #1 
Jun 2003
2^{4}·5·59 Posts 
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? 
20150103, 20:31  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}×7×163 Posts 
You probably have seen this, but just in case.
Somewhere else I think I noticed a comment that Magma does first 80 small primes before trying clever things (and so does your gfnsvCUDA for quadratic nonr). We can look up in Pari's code, too, but I vaguely remember hearing that it does the same... And between Magma and Pari, people surely care about efficiency so it seems like the tried and true way to approach the qnr. 
20150104, 03:49  #3 
Aug 2006
172C_{16} Posts 
I remember Bernstein has a clever algorithm for some nonresiduosity problem (quadratic, cubic, or general, I don't remember). He begins the paper, IIRC, by explaining that for all practical purposes you should search directly and that this algorithm is of theoretical interest only. This agrees with Batalov's post above.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New Computation  JohnFullspeed  Miscellaneous Math  8  20110713 10:54 
A computation worthy of the name  fivemack  Factoring  121  20100220 18:32 
New Pi Computation Record  ldesnogu  Lounge  11  20100107 14:42 
Value of computation  fivemack  Lounge  0  20080905 20:23 
Intersection with cubic  kuratkull  Miscellaneous Math  7  20080124 15:28 