Karim BELABAS on Wed, 27 Aug 2003 14:10:18 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Kronecker symbol |
On Mon, 25 Aug 2003, Jack Fearnley wrote: > I have been having some trouble with kronecker(x,y) which is described in the > documentation as a generalization of the Legendre symbol (x|y). I was > expecting kronecker to behave like a Dirichlet character. In particular, I > expected kronecker(3,4) to equal -1 whereas it computes as 1. > > I have two questions: > > 1) What is the precise definition of kronecker in Pari? Legendre symbol (x|y) extended to Z x Z by complete multiplicativity, plus the following special rules for y = 0, -1 or 2: y = 0: (x|0) = 1 if |x| = 1 0 otherwise y = -1: (x|-1) = 1 if x >= 0, -1 if x < 0. y = 2: (x|2) = 0 if x is even = 1 if x = 1, -1 mod 8 = -1 if x = 3, -3 mod 8 > 2) Is there a quick and easy way to generate quadratic Dirichlet characters > in Pari? Not really. You can use if (issquare(Mod(x, y)), 1, -1) [ assuming gcd(x,y) = 1 ], but issquare(x,y) requires factoring y in most cases and is very wasteful if the same y is used over and over again. [ better to factor it once and loop by hand over the cyclic components of (Z/yZ)^* ] > 2a) What about higher order Dirichlet characters? You have to program it yourself. Reduce to the case y prime, then the best solution depends on the size of y, the number of characters you need for a given y, available memory... and the actual efficiency required. A quick and very inefficient solution is to use znprimroot and znlog [ define an explicit isomorphism with additive characters of Z/(y-1)Z ] Cheers, Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]