Re: Quartic residue symbol

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* 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]
`