David R. Kohel on Tue, 11 Jan 2000 12:43:52 +1100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Bug in classno, qbfclassno? |
> On Mon, Jan 10, 2000 at 05:55:18PM +0100, Henri Cohen wrote: > > > > > classno(-174660)= 168 > > > classno(-272580)= 180 > > > > 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). > > > > Henri Cohen > > Powerful yet not flawless (at least implementation-wise) :-) > > ? setrand(1);quadclassunit(-108760)[1] > 48 > ? setrand(58);quadclassunit(-108760)[1] > 72 > > Thanks > > Igor When the factorization can be computed, the two-torsion group can be easily determined. This usually accounts for most of the noncyclicity, so the subgroup of squares is a better group in which to do BSGS. It is also has the advantage of being a potentially smaller group. Some further work, of course, is needed for a proof of correctness. Alternatively once a multiple m of the group exponent is determined, it is a trivial task to compute the smallest multiple of the form m/2^t before returning an answer. Similar post-BSGS verification can be done for other small primes p at which the group may have non-trival p-rank. --David