Karim Belabas on Mon, 18 Dec 2006 23:20:26 +0100

 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

@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]

`