20061017, 06:43  #1 
Mar 2003
New Zealand
1157_{10} Posts 
Computing nth power residue symbols
The current 1.2.x versions of sr5sieve checks whether terms of a sequence are quadratic residues before putting the sequence into the sieve. For version 1.3.x I am trying to extend this to check whether they are cubic, quartic or quintic residues too. For this to work I need to find a fast way to test, given a sequence k*b^n+c and that r divides p1, whether c*k*b^d is an rth power residue wrt p, for 0 <= d < r.
When r=2 this can be done with a single division then a lookup into a precomputed table of Legendre symbols to exclude those terms with Legendre symbol (ckb^d/p) = 1. For r in general it can be done by computing x_i=(1/b^i)^((p1)/r) (mod p) for 0 <= i < r once for each p, then computing y_k=k^((p1)/r) (mod p) once for each k that is a quadratic residue wrt p, then excluding those terms k*b^n+c with n=i (mod r) which don't satisfy x_i=y_k. I have a working prototype that implements this for r in {3,5}, but it actually results in a small slowdown (it takes longer to check whether sequences are cubic residues than the time saved by excluding 2/3 of them from the sieve). I am now looking for a faster algorithm to calculate the rth power symbol of a wrt p than computing a^((p1)/r) (mod p) with powmod(), but a faster powmod() would also help a little and might be enough to get a small speedup. (If the rth power symbol could be computed as fast as the Legendre symbol then something like 35% speedup could be achieved, but even doubling the speed of powmod would probably only get a 10% speedup at best). It is probably not possible to construct lookup tables for the cubic and quintic residue symbols, but the references I have seen when searching for cubic residues all seem to work in a ring of Eisenstein integers, and that sounds like I will need to do a bit of study to figure out how they relate to plain integers modulo a prime that the sieve works with. If anyone can help with ideas or references for making fast versions of these functions it would be a big help: Code:
uint64_t powmod(uint64_t a, uint64_t n, uint64_t p) { /* Return a^n (mod p). Assume 0 < a < p and n=(p1)/r, where p is a large prime and r is a small integer. If it helps then assume that the function will be called about 100 times with the same values of n and p. */ } Code:
int is_cubic_residue(uint64_t a, uint64_t p) { /* Return 1 if x^3=a (mod p) has a solution, 0 otherwise. Assume 0 < a < p where p is a large prime, 3(p1), and (a/p)=1. If it helps then it is OK to return a false 1 with low probability, but never a false 0. */ } Code:
int is_quartic_residue(uint64_t a, uint64_t p) /* As above, replace 3 with 4 */ int is_quintic_residue(uint64_t a, uint64_t p) /* As above, replace 3 with 5 */ 
20061017, 13:10  #2  
"Robert Gerbicz"
Oct 2005
Hungary
625_{16} Posts 
I'm also writing a sieve that will sieving k*b^n+c numbers. See your problems:
Quote:
Suppose also that k*b^n==1 mod p, where p is prime. There are two cases for each r(p1) prime value: if b^((p1)/r)!=1 mod p then you can find n mod r, suppose that n=x*r+y, where 0<=y<r k*b^n==1 mod p then / ^((p1)/r) you get: k^((p1)/r)*b^(y*(p1)/r)==1 mod p so k^((p1)/r)*(b^((p1)/r))^y==1 mod p. This equation is solvable in all cases, and there is only one y solution (mod r), because b^((p1)/r)!=1 mod p means that the order of b modulo p is divisible by r. It means that by baby step giant step method you can find the required y value for each remaining k value by O(sqrt(remaining*r)) mulmods, where remaining is the number of remaining k value. ( not counting the computation time of the required b^((p1)/r) and k^((p1)/r) mod p values!). If r is small then I'm using a table to see: if there is no n value for some k that n mod r=y then I eliminate that k value. If b^((p1)/r)==1 mod p then the equation: k^((p1)/r)==1 mod p, so if you compute this and this isn't true then you can eliminate that k value. You can extend this for primepowers r=q^h, where q is prime and h>1. Quote:
At the end you know some informations: n mod q^i mod p for each k value, you can solve these by Chinese remainder theorem: you will know n mod prod for each k value, where prod is the product of all q^i. Last fiddled with by R. Gerbicz on 20061017 at 13:24 

20061024, 00:09  #3 
Mar 2003
New Zealand
13·89 Posts 
Thanks for this explaination, I still have a way to go before I can implement it but I get the idea. I think it will supercede my approach, unless there is a fundamentally faster way to decide whether k is an rth power residue than computing k^((p1)/r).

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GPU Computing Cheat Sheet (a.k.a. GPU Computing Guide)  Brain  GPU Computing  20  20151025 18:39 
Residue classes  CRGreathouse  Math  4  20090312 16:00 
Are Legendre symbols proven to be defective?  jasong  Math  67  20080420 15:01 
The difference between P2P and distributed computing and grid computing  GP2  Lounge  2  20031203 14:13 
Masked residue  schneelocke  PrimeNet  6  20031122 01:26 