# Revision history [back]

Here Sage is letting PARI do the hard work, creating a "Buchmann's number field" (bnf), which is a data structure containing the defining data of the number field and invariants such as the class group structure. The linked page states about Class group, units, and the GRH that

Some of the functions starting with bnf are implementations of the sub-exponential algorithms for finding class and unit groups under GRH, due to Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier.

Some more names are dropped further along the page.

In the source code of PARI one sees that bnfinit corresponds to the C function bnfinit0 which calls Buchall_param, which seems to be doing much of the work. The source file credits McCurley and Buchmann. Probably it is easier to find a reference than it is to read Buchall_param.

Here Sage is letting PARI do the hard work, creating a "Buchmann's number field" (bnf), which is a data structure containing the defining data of the number field and invariants such as the class group structure. The linked page states about section Class group, units, and the GRH of the page I linked earlier states that

Some of the functions starting with bnf are implementations of the sub-exponential algorithms for finding class and unit groups under GRH, due to Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier.

Some more names are dropped further along the page.

In the source code of PARI one sees that bnfinit corresponds to the C function bnfinit0 which calls Buchall_param, which seems to be doing much of the work. The source file credits McCurley and Buchmann. Probably At this point it is probably it is easier to find a reference than it is to read Buchall_param.

Note that Sage's parameter proof tells PARI to run bnfcertify. From the same section quoted before:

Warning. Make sure you understand the above! By default, most of the bnf routines depend on the correctness of the GRH. In particular, any of the class number, class group structure, class group generators, regulator and fundamental units may be wrong, independently of each other. Any result computed from such a bnf may be wrong. The only guarantee is that the units given generate a subgroup of finite index in the full unit group. You must use bnfcertify to certify the computations unconditionally.

The source for bnfcertify0 refers to Zimmert's bound $B$ and consists of two phases. The first phase for the class group calls bnftestprimes and according to the User's Guide

Running this function successfully proves that the classes of all prime ideals of norm $\leq B$ belong to the subgroup of the class group generated by the factorbase used to compute the bnf (equal to the class group under GRH). If the condition is not true, then (GRH is false and) the function will run forever.

The second phase tests the units and relations, but I am not sure how.