Picard Groups and Refined Discrete Logarithms Authors: Werner Bley (werner.bley@math.uni-augsburg.de) Markus Endres (parigp@mendres.org) ================================================== This is a short guide to use our implementation for the computation of Picard groups and the refined discrete logarithm in PARI/GP. We also describe the function Conjecture() which leads to our conjecture described in the paper. For PARI/GP have a look at http://pari.math.u-bordeaux.fr/. 0. Using conditions ------------------- There is no license for using our source code or implemented algorithms. Feel free to use, change or distribute the source code. But don't delete the headers of the files. So, always keep the names of the authors of the original source code. Further it would be nice to get an email from you if you change anything. If you change a routine or if you have a better solution for any algorithm, ... please send an email to werner.bley@math.uni-augsburg.de and parigp@mendres.org Thanks a lot 1. Unzip and untar the file Picard.tar.gz ----------------------------------------- Our program runs under Linux. There is NO Windows version! No other Unix was tested. To use our files, unzip and untar the Picard.tar.gz file under Linux as follows: tar xfvz Picard.tar.gz This generates a directory called Picard with a lot of files inside. 2. Installation of PARI/GP -------------------------- ATTENTION: Use the unstable CVS version (at least 2.2.6) of PARI/GP, NOT the stable one. Our implementation DOESEN'T work with the stable version. We decided to use the unstable version on the strength of performance reasons. The unstable version is much faster than the stable one. But be carefull, sometimes PARI/GP crashes. We did a large amount of tests with the 2.2.6 version and it runs very well. The 2.2.8 (newest CVS version at the moment, Oct 2004) isn't stable enough to run our programms in a good manner. So, we recommend to use the version 2.2.6 of PARI/GP. Because of the use of the CVS version of PARI/GP this only works reliably under Linux. To install PARI/GP follow the instructions on http://pari.math.u-bordeaux.fr/. Here's a short description to get PARI/GP 2.2.6 from the Linux command shell with installed cvs: Login into the PARI/GP CVS server (there's no password): ? cvs -d :pserver:cvs@pari.math.u-bordeaux.fr:/home/cvs login Retrieve the version 2.2.6 of PARI/GP. This makes a local copy. ? cvs -z3 -d :pserver:cvs@pari.math.u-bordeaux.fr:/home/cvs checkout -r 2.2.6 pari Follow the instructions given in the INSTALL file of the PARI/GP files in your directory. If you don't have cvs installed on your system take a snapshot of PARI/GP from the PARI/GP homepage http://pari.math.u-bordeaux.fr/ 3. Start PARI/GP, load our files and use the online help -------------------------------------------------------- If you have done the installation of PARI/GP start the GP interpreter with the command 'gp' from a shell in the directory our files are saved. For using PARI/GP read the user guide on the PARI/GP homepage. To load and use our files and functions use the following command in the PARI/GP interpreter in the directory where all our gp-files are saved: \r init.gp This loads all necessary functions to compute Picard groups and discrete logarithms. In the PARI/GP interpreter you will get online help to all avalaible functions. Simply type ? and you'll get a detaild help for this function. 4. Hilbert and RunHilbert ------------------------- The function Hilbert(d) first computes the Hilbert class field L of K = Q(sqrt(d)). Then the ring of integers O_L is locally free over the integral group ring O_K[G], where G=Gal(L/K). We compute Pic(O_K[G]) and the discrete logarithm of the class of O_L. The function RunHilbert(low,high,h_min,h_max) calls Hilbert(d) for all fundamental discriminants d with low <= d < high and h_min <= h_K <= h_max. In order to reproduce the results in Hilbert.log, simply type gp < MakeHilbertLog.gp 4. Schertz and Ayala -------------------- The function SchertzAyala(bound,d) represents examples treated by Ayala and Schertz as described in the paper. bound is the number of primes you will consider and d=[-8,-11,-19,-43,-67,-163] the discriminant of the base field. 5. Our conjecture ----------------- For numerically verification of the conjecture described in our article 'Picard Groups and Refined Discrete Logarithms' start the routine Conjecture(bound,{d=0},{l=3},{inert=0},{logfile=0},{ivar=y},{greither=0}) with the arguments: bound : Compute bound primes with the corresponding property d : The discriminant of the base field K l : Field extension of degree l inert : Default false, i.e. take the splits logfile : Name for a logfile. This writes all output to logfile ivar : The variable of the defining polynomial of the base field. Don't change it, keep y! greither: For the Greither examples (d=[-7,-11,-19,-43,-67,-163]) we can use a faster method to compute (Rq/F)* and (R/F)*. To use this faster computation use greither=1. The braces means this argument is optional, i.e. the default argument will be taken. Lets do an example: Let K a number field with discriminant -7 and l=3. Then the kronecker symbol (d,l) is -1, i.e. 3 is inert in K/Q (Q the rationals). Now, search bound=5 prime ideals with (d,p)=1 (p splits) and p= 1 (mod 3): [37, 43, 67, 79, 109] Then the Picard group Pic(O_K[G]) = [2, [2]], i.e. the first component is the cardinality of Pic(O_K[G]) and the second one are the generators, where K[G] is the corresponding group ring. The class group of the field E will be computed as [1,[]] in the same matter as Pic(O_K[G]). Here is the result of Conjecture(5,-7,3) K.disc = -7 l = 3 (d,l) = -1 --> 3 inert in K/Q primes p with (d,p) = 1 and p = 1 (mod 3) : [37, 43, 67, 79, 109] Pic(O_K[G]) = [2 , [2]] E.clgp = [1 , []] p37 [O_L] in Pic(O_K[G]) = [1], theta((pi^e, alpha)) = [1], P^(l*theta) = []~ p37 [O_L] in Pic(O_K[G]) = [1], theta((pi^e, alpha)) = [1], P^(l*theta) = []~ p43 [O_L] in Pic(O_K[G]) = [1], theta((pi^e, alpha)) = [1], P^(l*theta) = []~ p43 [O_L] in Pic(O_K[G]) = [1], theta((pi^e, alpha)) = [1], P^(l*theta) = []~ p67 [O_L] in Pic(O_K[G]) = [0], theta((pi^e, alpha)) = [0], P^(l*theta) = []~ p67 [O_L] in Pic(O_K[G]) = [0], theta((pi^e, alpha)) = [0], P^(l*theta) = []~ p79 [O_L] in Pic(O_K[G]) = [0], theta((pi^e, alpha)) = [0], P^(l*theta) = []~ p79 [O_L] in Pic(O_K[G]) = [0], theta((pi^e, alpha)) = [0], P^(l*theta) = []~ p109 [O_L] in Pic(O_K[G]) = [1], theta((pi^e, alpha)) = [1], P^(l*theta) = []~ p109 [O_L] in Pic(O_K[G]) = [1], theta((pi^e, alpha)) = [1], P^(l*theta) = []~ Our conjecture holds. The class of O_L in Pic(O_K[G]) is equal to theta((pi^e,alpha)) as described in our paper. There are e.g. tow p37. These are the primes lying over p. Feel free to use our Conjecture(...) routine. Some examples are given in the file conjecture.log. The 'small' examples (l=3,l=5) can be computed in a short time (if you have a fast computer). For the large examples (l>5) be sure you have a very fast machine, a lot of phyical memory and a lot of time (up to 2 days). Further you need a lot of luck to run the unstable version of PARI/GP 'stable'! Sometimes it works. 6. Initialize a group ring -------------------------- To initialize a group ring you need a base field K (bnfinit), a group G (Ginit) and our routine GrInit(K,G,{ivar=x}) For the use of bnfinit have a look at the user guide of PARI/GP. Help for Ginit you'll get from the online help with ?Ginit and in the file GrInit.gp. The use and result of GrInit is described in the online help (?GrInit). 7. How to work with Modules --------------------------- To initialize a module use the function ModuleInit(grpring,M). This computes a lot of data for the module. For detailed information use the online help (?ModuleInit) and have a look at the source code. How to represent a module? Lets look at lambda:= sum(i=1,n,x_i,g_i), an element of the group ring K[G]. We represent such an element as an n-column vector with the coefficients x_i,i=1,...,n as entrys. So, a module generated by will be described as a matrix with the lambda_a as columns. 8. Computing a Picard group --------------------------- Computing Picard groups is very easy if you have the right routines. So, simply use our implemented function Picard(grpring,R,{flag=0},{greither=0}) which computes the Picard group for a given group ring grpring initialized with GrInit (6.). R is an order in the group ring. For a detailed description and the output of Picard(...) use the online help (?Picard in GP) and have a look at Picard.gp. 9. Solving the (refined) discrete logarithm ------------------------------------------- Solving the (refined) discret logarithm is as easy as computing Picard groups. Use our routine PicIsPrincipal(grpring,CR,a,{flag=1}) with the group ring as in Picard and CR the output of Picard(...). a is the locally free R-module and flag=1 means the refined discrete logarithm will be solved. For a detaild use of PicIsPrincipal(...) have a look at the online help (?PicIsPrincipal in GP) and at the file Picard.gp 10. The functions ---------------- For numerically verification of the conjecture given in our article you only need to know the routine Conjecture(...) as dpicard_lms escribed in 5. But there are a lot of functions in the background to do the computations in the Conjecture routine. At the head of each gp file is a short list and description of all avalaible functions in the corresponding file. Feel free to use and change our source code but always remember the using conditions in 0. For every function you get an online help in the PARI/GP interpreter with the ? command, i.e. gp> ?Conjecture will give you the information gp> Conjecture(bound,{d=0},{l=3},{inert=0},{logfile=0},{ivar=y},{greither=0}): This function verifys the conjecture given in the paper 'Picard groups and refined discrete logarithms'. ... Here's a short overview of the files and its contents: - init.gp : loads all files in the PARI/GP interpeter with \r init.gp - Conjecture.gp : implementation of the conjecture - Picard.gp : computation of the Picard group and the refined discrete logarithm - GrInit.gp : routines to work with group rings - Module.gp : routines to work with modules - NormalBasis.gp : computation of a normal basis and weak normal basis - ClassField.gp : computation of class fields - Oumf.gp : computation of the group quotient (R/F)* - Group.gp : computes the Smith Normal Form of a group - AAO.gp : computation of the arithmetic associated order and a locally free module - Ma.gp : for the computation of the class of Ma from delta(a) as described in the paper - Examples.gp : the routines Ayala, SchertzAyala and Greither to verify their results - Add.gp : some additional functions