Skip to Main content Skip to Navigation

Arithmétique efficace des extensions de corps finis

Abstract : Finite fields are ubiquitous in cryptography and coding theory, two fields that are of utmost importance in modern communications. For that reason, it is crucial to represent finite fields and compute in them in the most efficient way possible. In this thesis, we investigate the arithmetic of finite field extensions in two different and independent ways.In the first part, we study the arithmetic of one fixed finite field extension F_{p^k}. When estimating the complexity of an algorithm in a finite field extension, we often count the arithmetic operations that are needed in the base field F_p. In such a model, all operations have the same unit cost. This is known as the algebraic complexity model. Nevertheless, it is known that multiplications are more expensive, i.e. take more time, than additions. For that reason, alternative models were studied, such as the bilinear complexity model, in which the assumption is that additions have no cost, thus we only count the multiplications. To have an efficient multiplication algorithm in the extension F_{p^k}, research has been done to obtain formulas in which the number of multiplications in the base field F_p are minimized. The optimal number of such multiplication is, by definition, the bilinear complexity of the multiplication in F_{p^k}. Finding the exact value of the bilinear complexity of the multiplication in finite field extensions is hard, but there exist algorithms to find optimal formulas in small dimension. Asymptotically, there exist different algorithms that give formulas that are not necessarily optimal but still give a linear upper bound on the bilinear complexity in the degree of the extension. We generalize these results to a new kind of complexity, called the hypersymmetric complexity, that is linked with formulas possessing extra properties of symmetry. We provide an ad hoc algorithm finding hypersymmetric formulas in small dimension, as well as an implementation and experimental results. Generalizing the proofs of the literature, we also prove that the hypersymmetric complexity is still linear in the degree of the extension.In the second part, we work with multiple finite field extensions simultaneously. In most computer algebra systems, it is possible to deal with finite fields, but two arbitrary extensions are often seen as independent objects, and the links between them are not necessarily accessible to the user. Our goal in this part is to construct an efficient data structure to represent multiple extensions, and the embeddings between them. We also want the embeddings to be compatible, i.e. if we have three integers a, b, c such that a | b | c, we want the composition of the embeddings from F_{p^a} to F_{p^b} and F_{p^b} to F_{p^c} to be equal to the embedding from F_{p^a} to F_{p^c}. We call this data structure a lattice of compatibly embedded finite fields. We provide an implementation of the Bosma-Canon-Steel framework, a lattice of compatibly embedded finite fields that was only available in MAGMA, as well as experimental results. After this work, we also added the Bosma-Canon-Steel framework to the computer algebra system Nemo.Another popular method to obtain lattices of compatibly embedded finite fields is to use Conway polynomials. It is quite efficient but the extensions have to be defined using these precomputed special polynomials to obtain compatibility between embeddings. Inspired by both the Bosma-Canon-Steel framework and the Conway polynomials, we construct a new kind of lattice, that we call standard lattice of compatibly embedded finite fields. This construction allows us to use arbitrary finite field extensions, while being rather efficient. We provide a detailed complexity analysis of the algorithms involved in this construction, as well as experimental results to show that the construction is practical.
Complete list of metadata
Contributor : ABES STAR :  Contact
Submitted on : Monday, July 26, 2021 - 2:46:12 PM
Last modification on : Wednesday, January 26, 2022 - 2:38:50 PM
Long-term archiving on: : Wednesday, October 27, 2021 - 6:23:16 PM


Version validated by the jury (STAR)


  • HAL Id : tel-03299466, version 1


Édouard Rousseau. Arithmétique efficace des extensions de corps finis. Number Theory [math.NT]. Institut Polytechnique de Paris, 2021. English. ⟨NNT : 2021IPPAT013⟩. ⟨tel-03299466⟩



Record views


Files downloads