Paper 2016/531
Reducing number field defining polynomials: An application to class group computations
Alexandre Gélin and Antoine Joux
Abstract
In this paper, we describe how to compute smallest monic polynomials that define a given number field $\mathbb K$. We make use of the onetoone correspondence between monic defining polynomials of $\mathbb K$ and algebraic integers that generate $\mathbb K$. Thus, a smallest polynomial corresponds to a vector in the lattice of integers of $\mathbb K$ and this vector is short in some sense. The main idea is to consider weighted coordinates for the vectors of the lattice of integers of $\mathbb K$. This allows us to find the desired polynomial by enumerating short vectors in these weighted lattices. In the context of the subexponential algorithm of Biasse and Fieker for computing class groups, this algorithm can be used as a precomputation step that speeds up the rest of the computation. It also widens the applicability of their faster conditional method  which requires a defining polynomial of small height  to a much larger set of number field descriptions.
Note: Submitted to the Twelfth Algorithmic Number Theory Symposium (ANTSXII)
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 number theoryclass group computation
 Contact author(s)
 alexandre gelin @ uvsq fr
 History
 20180611: revised
 20160531: received
 See all versions
 Short URL
 https://ia.cr/2016/531
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/531, author = {Alexandre Gélin and Antoine Joux}, title = {Reducing number field defining polynomials: An application to class group computations}, howpublished = {Cryptology ePrint Archive, Paper 2016/531}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/531}}, url = {https://eprint.iacr.org/2016/531} }