Re: Bug in classno, qbfclassno?

["David R. Kohel" <kohel@maths.usyd.edu.au>]

> 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