Efficient computation of cubic residue

axn · 2015-01-02, 06:29

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?

Batalov · 2015-01-03, 20:31

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.

CRGreathouse · 2015-01-04, 03:49

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.

2015-01-02, 06:29	#1
axn Jun 2003 2·7·17·23 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^((p-1)/3) == 1, but is there a faster method? Alternatively, how can I efficiently find a cubic non residue (mod p) without searching?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New Computation	JohnFullspeed	Miscellaneous Math	8	2011-07-13 10:54
A computation worthy of the name	fivemack	Factoring	121	2010-02-20 18:32
New Pi Computation Record	ldesnogu	Lounge	11	2010-01-07 14:42
Value of computation	fivemack	Lounge	0	2008-09-05 20:23
Intersection with cubic	kuratkull	Miscellaneous Math	7	2008-01-24 15:28

2015-01-03, 20:31	#2
Batalov "Serge" Mar 2008 San Diego, Calif. 10403₁₀ 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.

2015-01-04, 03:49	#3
CRGreathouse Aug 2006 2²×3×499 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.