Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around. / Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.

Deligne and Howe described polarized abelian varieties over finite fields in terms of finitely generated free Z-modules satisfying a list of easy to state axioms. In this thesis we address the problem of developing an effective algorithm to compute isomorphism classes of (principally) polarized abelian varieties over a finite field, together with their automorphism groups. Performing such computations requires the knowledge of the ideal classes (both invertible and non-invertible) of certain orders in number fields. Hence we describe a method to compute the ideal class monoid of an order and we produce concrete computations in dimension 2, 3 and 4.

No description available.

Systems biology aims at system-level understanding of biological systems, in particular cellular networks. The milestones of this understanding are knowledge of the structure of the system, understanding of its dynamics, effective control methods, and powerful prediction capability. The complexity of biological systems makes it inevitable to consider mathematical modeling in order to achieve these goals. The enormous accumulation of experimental data representing the activities of the living cell has triggered an increasing interest in the reverse engineering of biological networks from data. In particular, construction of discrete models for reverse engineering of biological networks is receiving attention, with the goal of providing a coarse-grained description of such networks. In this dissertation we consider the modeling framework of polynomial dynamical systems over finite fields constructed from experimental data. We present and propose solutions to two problems inherent in this modeling method: the necessity of appropriate discretization of the data and the selection of a particular polynomial model from the set of all models that fit the data. Data discretization, also known as binning, is a crucial issue for the construction of discrete models of biological networks. Experimental data are however usually continuous, or, at least, represented by computer floating point numbers. A major challenge in discretizing biological data, such as those collected through microarray experiments, is the typically small samples size. Many methods for discretization are not applicable due to the insufficient amount of data. The method proposed in this work is a first attempt to develop a discretization tool that takes into consideration the issues and limitations that are inherent in short data time courses. Our focus is on the two characteristics that any discretization method should possess in order to be used for dynamic modeling: preservation of dynamics and information content and inhibition of noise. Given a set of data points, of particular importance in the construction of polynomial models for the reverse engineering of biological networks is the collection of all polynomials that vanish on this set of points, the so-called ideal of points. Polynomial ideals can be represented through a special finite generating set, known as Gröbner basis, that possesses some desirable properties. For a given ideal, however, the Gröbner basis may not be unique since its computation depends on the choice of leading terms for the multivariate polynomials in the ideal. The correspondence between data points and uniqueness of Gröbner bases is studied in this dissertation. More specifically, an algorithm is developed for finding all minimal sets of points that, added to the given set, have a corresponding ideal of points with a unique Gröbner basis. This question is of interest in itself but the main motivation for studying it was its relevance to the construction of polynomial dynamical systems. This research has been partially supported by NIH Grant Nr. RO1GM068947-01. / Ph. D.

In order to understand biochemical networks we need to know not only how their parts work but also how they interact with each other. The goal of systems biology is to look at biological systems as a whole to understand how interactions of the parts can give rise to complex dynamics. In order to do this efficiently, new techniques have to be developed. This work shows how tools from mathematics are suitable to study problems in systems biology such as modeling, dynamics prediction, reverse engineering and many others. The advantage of using mathematical tools is that there is a large number of theory, algorithms and software available. This work focuses on how algebra can contribute to answer questions arising from systems biology. / Ph. D.

On s'intéresse dans cette thèse à la détermination du rang de tenseur de la multiplication dans $mathbb{F}_{q^n}$, l'extension de degré $n$ du corps fini $mathbb{F}_q$ ; ce rang de tenseur correspond en particulier à la complexité bilinéaire de la multiplication dans $mathbb{F}_{q^n}$ sur $mathbb{F}_q$. Dans cette optique, on présente les différentes évolutions de l'algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky et qui a permis d'établir que le rang de tenseur de la multiplication dans $mathbb{F}_{q^n}$ était linéaire en~$n$. Cet algorithme en fournit désormais les meilleures bornes connues dans le cas d'extensions de degré grand relativement au cardinal du corps de base — le cas des petites extensions étant bien connu. Afin d'obtenir des bornes uniformes en le degré de l'extension, il est nécessaire, pour chaque $n$, de déterminer un corps de fonctions algébriques qui convienne pour appliquer l'algorithme pour $mathbb{F}_{q^n}$, c'est-à-dire qui ait suffisamment de places de petit degré relativement à son genre $g$ et pour lequel on puisse établir l'existence de diviseurs ayant certaines propriétés, notamment des diviseurs non-spéciaux de degré ${g-1}$ ou de dimension nulle et de degré aussi près de ${g-1}$ que possible ; c'est pourquoi les tours de corps de fonctions sont d'un intérêt considérable. En particulier, on s'intéresse ici à l'étude des tours de Garcia-Stichtenoth d'extensions d'Artin-Schreier et de Kummer qui atteignent la borne de Drinfeld-Vlu{a}duc{t}. / In this thesis, we focus on the determination of the tensor rank of multiplication in $mathbb{F}_{q^n}$, the degree $n$ extension of the finite field $mathbb{F}_q$, which corresponds to the bilinear complexity of multiplication in $mathbb{F}_{q^n}$ over $mathbb{F}_q$. To this end, we describe the various successive improvements to the evaluation-interpolation algorithm introduced in 1987 by D.V. and G.V. Chudnovsky which shows the linearity of the tensor rank of multiplication in $mathbb{F}_{q^n}$ with respect to $n$. This algorithm gives the best known bounds for large degree extensions relative to the cardinality of the base field (the case when the degree of the extension is small is well known). In order to obtain uniform bounds, we need to determine, for each $n$, a suitable algebraic function field for the algorithm on $mathbb{F}_{q^n}$, namely a function field with sufficiently many places of small degree relative to its genus $g$ and for which we can prove the existence of divisors with some good properties such as non-special divisors of degree ${g-1}$ or zero-dimensional divisors with degree as close to ${g-1}$ as possiblestring; these conditions lead us to consider towers of algebraic function fields. In particular, we are interested in the study of Garcia-Stichtenoth towers of Artin-Schreier and Kummer extensions which attain the Drinfeld-Vlu{a}duc{t} bound.

The thesis deals with arithmetics of elliptic curves over finite fields and methods to improve those calculations. In the first part, algebraic geometry helps to define elliptic curves and derive their basic properties including the group law. The second chapter seeks ways to speed up these calculations by means of time-memory tradeoff, i.e. adding redundancy. At last, the third part introduces a wholly new curve form, which is particularly effective for such purposes.

In the present work is presented a brief data collection about the history of prime numbers and how this subject is shown in the new scenario brought by BNCC (Common Curricular National Base) . It was proved the Fundamental Arithmetic Theorem and it was presented two important ways to calculate that are the Congruence and the Fermet Theorem. It is given a teaching method and a differentiated material to be used in class. / Neste trabalho é apresentado um breve levantamento da história dos números primos e de que maneira o assunto acerca desses números aparecem no novo cenário trazido pela BNCC. Provamos o Teorema Fundamental da Aritmética e apresentamos duas ferramentas importantes de cálculo, que são as Congruências e o Pequeno Teorema de Fermat. Apresentamos ainda uma proposta didática e um material diferenciado para ser utilizado em sala de aula.

Cette thèse traite de la synchronisation des systèmes dynamiques.La synchronisation est étudiée pour une configuration de type maître-esclave, c'est-à-dire pour des systèmes couplés de façon unidirectionnelle. Ce type de configuration s'avère d'un intérêt tout particulier car elle correspond à des architectures de communications chiffrées un-vers-un ou un-vers-plusieurs. Une attention spécifique est portée sur l'autosynchronisation, comportement qui caractérise la synchronisation par le simple couplage maître-esclave et donc en l'absence de tout contrôle extérieur. Elle joue un rôle majeur dans les communications impliquant des chiffreurs par flot autosynchronisants. L'étude de l'autosynchronisation dans le contexte cryptographique s'appuie sur la théorie du contrôle. Un lien original entre l'autosynchronisation et le principe de chiffrement/déchiffrement en cryptographie est mis en évidence. Il fait appel à la propriété de platitude des systèmes dynamiques, un concept emprunté à l'automatique. On montre que les systèmes dynamiques plats définissent complètement l'ensemble des systèmes autosynchronisants et permettent d'élargir les structures existantes des chiffreurs autosynchronisants. La platitude est tout d'abord étudiée pour deux types de systèmes non linéaires~: les systèmes linéaires commutés et à paramètres variants (LPV). La caractérisation des sorties plates s'appuie sur le concept de semigroupes nilpotents et un algorithme performant est proposé. Une approche constructive pour réaliser des structures maître-esclave autosynchronisantes est proposée sur la base de systèmes plats et les notions d'inversibilité à gauche et à droite empruntées à la théorie du contrôle. Par la suite, l'autosynchronisation est étudiée dans le contexte booléen, privilégié en cryptographie.Elle est caractérisée en premier lieu au travers la notion d'influence. Ensuite, différentes représentations matricielles associées aux fonctions booléennes sont proposées. Ces représentations s'avèrent particulièrement intéressantes pour l'analyse des propriétés liées à la sécurité. Un lien entre l'autosynchronisation et les structures propres des représentations matricielles est établi. Une approche orientée graphes est finalement élaborée pour la caractérisation. De nouvelles constructions de structures autosynchronisantes en sont déduites et des éléments de sécurité sont discutés. Enfin, une plateforme de test à base de FPGA qui a été réalisée est décrite / This thesis deals with the synchronization of dynamical systems. The synchronization considered is called master-slave, that is, the dynamical systems are connected in a unidirectional way. This configuration is of interest because it corresponds to an architecture encountered in secured communications of type one-to-one or one-to-many. A special attention is paid to self-synchronization. A behaviour that characterizes synchronization achieved with a simple master-slave coupling and so, without any external control. It is a central feature of self-synchronizing stream ciphers. The study of self-synchronization in the cryptographic context relies on control theory. An original connection between self-synchronization and encryption/decryption is provided. It is based on the flatness property of dynamical systems, a property borrowed from automatic control. It is shown that flat dynamical systems completly define the set of all self-synchronizing systems and thus, enlarge the existing structures of self-synchronizing stream ciphers. Flatness is first of all studied for the case of two nonlinear systems: switched linear systems and linear parameter-varying (LPV) systems. Flatness caracterization is based on the concept of nilpotent semigroups and an efficient algorithm is provided. A constructive approach for self-synchronizing master-slave structures is proposed. It relies on the construction of flat systems as well as on left and right invertibility also borrowed from control theory. Then, self-synchronization is studied in the Boolean context which is preferred in cryptography. Self-synchronization is caracterized through the notion of influence. Several matrix representations of Boolean functions are proposed. These representations are especially interesting for security analysis. A connection between self-synchronization and the eigenstructures of these matrices is established. Then, a graph oriented approach is provided. New self-synchronizing constructions are deduced and security elements are discussed. Eventually, the description of a realized FPGA based test plateform is provided

La sécurité des systèmes cryptographiques à clef publique repose sur la difficulté de résoudre certains problèmes mathématiques, parmi lesquels se trouve le problème du logarithme discret sur les corps finis GF(p^n). Dans cette thèse, nous étudions les variantes de l’algorithme de crible algébrique, number field sieve (NFS) en anglais, qui résolvent le plus rapidement ce problème, dans le cas où la caractéristique du corps est dite moyenne. NFS peut être divisé en quatre étapes principales : la sélection polynomiale, la recherche de relations, l’algèbre linéaire et le calcul d’un logarithme individuel. Nous décrivons ces étapes, en insistant sur la recherche de relations, une des étapes les plus coûteuses. Une des manières efficaces de réaliser cette étape est d’utiliser des algorithmes de crible. Contrairement au cas classique où la recherche de relations est réalisée dans un espace à deux dimensions, les corps finis que nous ciblons requièrent une énumération d’éléments dans un espace de plus grande dimension pour atteindre la meilleure complexité théorique. Il existe des algorithmes de crible efficaces en deux dimensions, mais peu pour de plus grandes dimensions. Nous proposons et analysons deux nouveaux algorithmes de crible permettant de traiter n’importe quelle dimension, en insistant particulièrement sur la dimension trois. Nous avons réalisé une implémentation complète de la recherche de relations pour plusieurs variantes de NFS en dimensions trois. Cette implémentation, qui s'appuie sur nos nouveaux algorithmes de crible, est diffusée au sein du logiciel CADO-NFS. Nous avons pu valider ses performances en nous comparant à des exemples de la littérature. Nous avons également été en mesure d’établir deux nouveaux records de calcul de logarithmes discrets, l'un dans un corps GF(p^5) de taille 324 bits et l'autre dans un corps GF(p^6) de taille 422 bits / The security of public-key cryptography relies mainly on the difficulty to solve some mathematical problems, among which the discrete logarithm problem on finite fields GF(p^n). In this thesis, we study the variants of the number field sieve (NFS) algorithm, which solve the most efficiently this problem, in the case where the characteristic of the field is medium. The NFS algorithm can be divided into four main steps: the polynomial selection, the relation collection, the linear algebra and the computation of an individual logarithm. We describe these steps and focus on the relation collection, one of the most costly steps. A way to perform it efficiently is to make use of sieve algorithms. Contrary to the classical case for which the relation collection takes place in a two-dimensional space, the finite fields we target require the enumeration of elements in a higher-dimensional space to reach the best theoretical complexity. There exist efficient sieve algorithms in two dimensions, but only a few in higher dimensions. We propose and study two new sieve algorithms allowing us to treat any dimensions, with an emphasis on the three-dimensional case. We have provided a complete implementation of the relation collection for some variants of the NFS in three dimensions. This implementation relies on our new sieve algorithms and is distributed in the CADO-NFS software. We validated its performances by comparing with examples from the literature. We also establish two new discrete logarithm record computations, one in a 324-bit GF(p^5) and one in a 422-bit GF(p^6)