mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2015-01-02, 06:29   #1
axn
 
axn's Avatar
 
Jun 2003

10010101010012 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
Old 2015-01-03, 20:31   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

915610 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2015-01-04, 03:49   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:40.

Wed Nov 25 23:40:16 UTC 2020 up 76 days, 20:51, 3 users, load averages: 1.66, 1.31, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.