Re: Enumeration approach to computing class groups

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Wed, Jun 16, 2021 at 04:08:58PM +0000, David Marquis wrote:
> Dear PARI developers,
> 
> I am currently writing a review of the literature on index calculus
> class group algorithms as part the work for my PhD thesis.
> 
> One of the papers in the literature is Improved Techniques For
> Computing The Ideal Class Group And A System Of Fundamental Units In
> Number Fields by Biasse and Fieker.
> 
> A modified version of the PARI’s index calculus algorithm (normally
> called by the bnfinit function) is used in this paper. In the best
> implementation they came up with PARI is used to generate relations
> for index calculus. They indicate that PARI’s bnfinit function uses an
> enumeration of short vectors to construct relations.

Hello David,

In general be wary of any performance claim when no implementation is
provided.

> I have briefly looked at the PARI code and I think the enumeration
> approach they mean is the essentially the function Fincke_Pohst_ideal
> in the file buch2.c.  My guess is that this was added or modified
> somehow in the PARI 2.7 release.

Fincke_Pohst_ideal was added in PARI 2.6.1 in the following git commit:

commit c850d5dc81ebd7a0c798470c6430bbe0c0fe9ed6
Author: Loic Grenie <loic.grenie@gmail.com>
Date:   Mon Mar 28 12:59:56 2011 +0200

There are a lot of improvements that have been implemented since that
time.

> I am wondering if any description of this method of constructing
> relations is available. This note
> http://pari.math.u-bordeaux1.fr/Events/PARI2012/talks/bnfinit.pdf by
> Loïc Grenié is the closest thing I could find but it does not get as
> far as describing the enumeration approach in bnfinit.

I do not have any better reference, but this is straightforward:
Given an ideal, we need to find elements of small (algebraic) norm 
inside.
Since nobody knows how to do that (except for quadratic fields),
we search for elements of small T_2 norm, for which LLL applies.
What Fincke_Pohst_ideal does is to is use Fincke-Pohst algorithm
to enumerate small elements for the T_2 norms inside the ideal.
This is an exponential time algorithm normally, so we add counters
and abort as soon as some counter reaches some predetermined threshold.
The hope is that with the right threshold values, we get relations
faster than with just LLL (that is, we spend more time on each ideals,
but find more relations on average, so we are globally faster).
One of the benefit is that finding new ideals to process is not entirely
free, so needing less ideals overall can be advantageous.

Cheers,
Bill.