Enumeration approach to computing class groups

David Marquis <[email protected]>
Newsgroups gmane.comp.mathematics.pari.devel
Message-ID <[email protected]>
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.

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.

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.

Best,
David
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.