Karim Belabas on Mon, 18 Dec 2006 23:20:26 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Quartic residue symbol |
* Iftikhar Burhanuddin [2006-09-25 06:07]: > I'm in need of some gp code which will compute the quartic/biquadratic > residue symbol. The symbol is defined as follows [Ireland-Rosen page 122]: > > Let Z[i] be the ring of Gaussian integers and let pi be an irreducible in > Z[i]. Let N(pi) denote the size of finite field Z[i]/pi Z[i]. Let T(pi) = > (N(pi)-1)/4. > > If a \in Z[i], such that pi does not divide a, and (pi) not equal to > (1+i), there exists a unique integer j, 0 <= j <=3 such that > a^T(pi) congruent to i^j (pi). > > The quartic residue symbol for a and pi is defined as (a/pi)_4 := i^j > > The following script factors Gaussian integers into Gaussian primes and > hence I have a way of generating the irreducibles. > > http://www.research.att.com/~njas/sequences/a078458.txt > > Apart from setting up nfinit(y^2+1) and don't know how to proceed with the > arithmetic. Any help will be greatly appreciated! Sorry for a very late answer, I had somehow missed this post. 1) The _very_ basic algorithm using no more than the definition is: symb(a, pr) = { local(t, modpr); modpr = nfmodprinit(nf, pr); t = nfeltpowmodpr(nf, a, (idealnorm(nf,pr)-1)/4, modpr); t = centerlift(Mod(1,pr.p)*t); t[1] + t[2] * I } (23:03) gp > nf = nfinit(y^2+1); pr = idealprimedec(nf, 10000000019)[1]; (23:03) gp > symb(y, pr) %2 = -1 (23:03) gp > symb(1+y, pr) %3 = -I (23:03) gp > symb(2+3*y, pr) %4 = 1 2) The basic algorithm uses the quartic reciprocity law. It's a nice exercise. 3) The not-so-basic algorithm in essentially linear time, using ideas from the half-gcd algorithm is left as a rather painful exercise to the reader. See, e.g. @article {MR1931197, AUTHOR = {Weilert, Andr{\'e}}, TITLE = {Fast computation of the biquadratic residue symbol}, JOURNAL = {J. Number Theory}, FJOURNAL = {Journal of Number Theory}, VOLUME = {96}, YEAR = {2002}, NUMBER = {1}, PAGES = {133--151}, ISSN = {0022-314X}, CODEN = {JNUTA9}, MRCLASS = {11A55 (11A15)}, MRNUMBER = {1 931 197}, } Hope this helps, K.B. NB: In current PARI versions (e.g. 2.3.* or 2.4.*), you can factor Gaussian integers using 'factor' directly (22:37) gp > factor(100+I) %1 = [-I 1] [8 + 3*I 1] [4 + 11*I 1] -- Karim Belabas Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] `