ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 10 Aug 2018 18:35:49 +0200Algorithm for computing Class Group and Class Number?https://ask.sagemath.org/question/43310/algorithm-for-computing-class-group-and-class-number/I wanted to know what procedure does SAGE use for computing class numbers. I typed
sage : K = NumberField(x^2 + x + 1)
sage : K.class_number?
After that I got the documentation and further I opened this file
~/SageMath/local/lib/python2.7/site-packages/sage/rings/number_field/**number_field.py**
In that I looked for the place where I can find the class number snippet. It turns out that sage returns the order of class group, so I looked for class group snippet.
proof = proof_flag(proof)
try:
return self.__class_group[proof, names]
except KeyError:
pass
except AttributeError:
self.__class_group = {}
k = self.pari_bnf(proof)
cycle_structure = tuple( ZZ(c) for c in k.bnf_get_cyc() )
# Gens is a list of ideals (the generators)
gens = tuple( self.ideal(hnf) for hnf in k.bnf_get_gen() )
G = ClassGroup(cycle_structure, names, self, gens, proof=proof)
self.__class_group[proof, names] = G
return G
But I couldn't understand where is the implementation of algorithm. Can anyone help me from here to reach where I can get the algorithm?Fri, 10 Aug 2018 15:54:14 +0200https://ask.sagemath.org/question/43310/algorithm-for-computing-class-group-and-class-number/Answer by rburing for <p>I wanted to know what procedure does SAGE use for computing class numbers. I typed </p>
<p>sage : K = NumberField(x^2 + x + 1)</p>
<p>sage : K.class_number?</p>
<p>After that I got the documentation and further I opened this file
~/SageMath/local/lib/python2.7/site-packages/sage/rings/number_field/<strong>number_field.py</strong></p>
<p>In that I looked for the place where I can find the class number snippet. It turns out that sage returns the order of class group, so I looked for class group snippet. </p>
<p>proof = proof_flag(proof) </p>
<pre><code> try:
return self.__class_group[proof, names]
except KeyError:
pass
except AttributeError:
self.__class_group = {}
k = self.pari_bnf(proof)
cycle_structure = tuple( ZZ(c) for c in k.bnf_get_cyc() )
# Gens is a list of ideals (the generators)
gens = tuple( self.ideal(hnf) for hnf in k.bnf_get_gen() )
G = ClassGroup(cycle_structure, names, self, gens, proof=proof)
self.__class_group[proof, names] = G
return G
</code></pre>
<p>But I couldn't understand where is the implementation of algorithm. Can anyone help me from here to reach where I can get the algorithm?</p>
https://ask.sagemath.org/question/43310/algorithm-for-computing-class-group-and-class-number/?answer=43318#post-id-43318Here Sage is [letting PARI do the hard work](https://pari.math.u-bordeaux.fr/dochtml/html/General_number_fields.html), 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 section [Class group, units, and the GRH](https://pari.math.u-bordeaux.fr/dochtml/html/General_number_fields.html#se:GRHbnf) 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`](https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=blob;f=src/basemath/buch2.c;h=2f8b56c1c56e84de66dfa19d7642bb882950a944;hb=HEAD#l3976), which seems to be doing much of the work. The source file credits McCurley and Buchmann. 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`](https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi?p=pari.git;a=blob;f=src/basemath/buch3.c;h=60220887845a93c362988b9b66f7cd9677e6ebd6;hb=HEAD#l1146) 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.Fri, 10 Aug 2018 18:35:49 +0200https://ask.sagemath.org/question/43310/algorithm-for-computing-class-group-and-class-number/?answer=43318#post-id-43318