mersenneforum.org Efficient computation of cubic residue
 Register FAQ Search Today's Posts Mark Forums Read

 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?
 2015-01-03, 20:31 #2 Batalov     "Serge" Mar 2008 San Diego, Calif. 1040310 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 22×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.

 Similar Threads Thread Thread Starter Forum Replies Last Post JohnFullspeed Miscellaneous Math 8 2011-07-13 10:54 fivemack Factoring 121 2010-02-20 18:32 ldesnogu Lounge 11 2010-01-07 14:42 fivemack Lounge 0 2008-09-05 20:23 kuratkull Miscellaneous Math 7 2008-01-24 15:28

All times are UTC. The time now is 16:56.

Sun Oct 1 16:56:41 UTC 2023 up 18 days, 14:39, 0 users, load averages: 1.28, 1.01, 0.94