Karim BELABAS on Thu, 17 Feb 2000 13:26:09 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Bug in classno, qbfclassno? |
>> > [Fernando Rodriguez-Villegas:] >> > classno(-174660)= 168 >> > classno(-272580)= 180 >> [Henri Cohen] >> This function (written by me) should definitely be removed, or rewritten >> correctly. It is based on a naive version of Shanks baby step giant step >> method which assumes that the approximate class number obtained by an >> Euler product is good enough, and that the class group is not too far >> from cyclic. The main reason for the bug is that the class group has >> large 2 rank. It is not difficult to write a correct baby step giant step >> method which completely avoids this (one has to take into account the >> full group structure, and I give the algorithm in my GTM 138 book, >> starting from the second printing, the first printing has serious >> errors), but in 10 years I have been lazy to do so because of the much >> more powerful quadclassunit algorithms based on Hafner-McCurley >> subexponential methods (assuming GRH). >[Igor] > >Powerful yet not flawless (at least implementation-wise) :-) > >? setrand(1);quadclassunit(-108760)[1] >48 >? setrand(58);quadclassunit(-108760)[1] >72 According to the documentation: (??quadclassunit) ---------------------------------------------------------------------------- Optional parameter tech is a row vector of the form [c_1,c_2], where c_1 and c_2 are positive real numbers which control the execution time and the stack size. To get maximum speed, set c_2 = c. To get a rigorous result (under GRH) you must take c_2 = 6. Reasonable values for c are between 0.1 and 2. ^^^^^^^^^^^^^^^^^^^^^ ---------------------------------------------------------------------------- In other words, by default, for the sake of speed (and sometimes, of feasability...), none of the PARI classgroup functions have a guaranteed output, even under GRH, because they replace Bach's bound by a small multiple (about 1/50 times the correct bound). In fact : ? setrand(58);quadclassunit(-108760, , [0.1, 6])[1] 48 (in this case it doesn't make a real difference in running times since the answer is nearly instantaneous, but it's still about twice slower) Karim. __ Karim Belabas email: Karim.Belabas@math.u-psud.fr Dep. de Mathematiques, Bat. 425 Universite Paris-Sud Tel: (00 33) 1 69 15 57 48 F-91405 Orsay (France) Fax: (00 33) 1 69 15 60 19 -- PARI/GP Home Page: http://hasse.mathematik.tu-muenchen.de/ntsw/pari/