In this thesis we study the number of periodic points of congruential monomial dynamical system. By concept of index calculus we are able to calculate the number of solutions for congruential equations. We give formula for the number of r-periodic points over prime power. Then we discuss about calculating the total number of periodic points and cycles of length r for prime power.

Seit W. Diffie und M. Hellman im Jahr 1976 ihren Ansatz für einen sicheren kryptographischen Schlüsselaustausch vorgestellten, ist der sogenannte Diskrete Logarithmus zu einem zentrales Thema der Kryptoanalyse geworden. Dieser stellt eine Erweiterung des bekannten Logarithmus auf beliebige endliche Gruppen dar. In der vorliegenden Dissertation werden zwei von C. Diem eingeführte Algorithmen untersucht, mit deren Hilfe der diskrete Logarithmus in der Picardgruppe glatter, nichthyperelliptischer Kurven vom Geschlecht g > 3 bzw. g > 4 über endlichen Körpern berechnet werden kann. Beide Ansätze basieren auf der sogenannten Indexkalkül-Methode und benutzen zur Erzeugung der dafür benötigten Relationen spezielle Linearsysteme, welche durch Schneiden von ebenen Modellen der Kurve mit Geraden erzeugt werden. Um Aussagen zur Laufzeit der Algorithmen tätigen zu können, werden verschiedene Sätze über die Geometrie von Kurven bewiesen. Als zentrale Aussage wird zum einem gezeigt, dass ebene Modelle niedrigen Grades effizient berechnet werden können. Zum anderen wird bewiesen, dass sich bei genügend großem Grundkörper die Anzahl der vollständig über dem Grundkörper zerfallenden Geraden wie heuristisch erwartet verhällt. Für beide Aussagen werden dabei Familien von Kurven betrachtet und diese gelten daher uniform für alle glatten, nichthyperelliptischen Kurven eines festen Geschlechts. Die genannten Resultate führen schlussendlich zu dem Beweis einer erwarteten Laufzeit von O(q^(2-2/(g-1))) für den ersten der beiden Algorithmen, wobei q die Anzahl der Elemente im Grundkörper darstellt. Der zweite Algoritmus verbessert dies auf eine heuristische Laufzeit in O(q^(2-2/(g-2))), imdem er Divisoren von höherem Spezialiätsgrad erzeugt. Es wird bewiesen, dass dieser Ansatz für einen uniform gegen 1 konvergierenden Anteil an glatten, nichthyperelliptischen Kurven eines festen Geschlechts über Grundkörpern großer Charakteristik eine große Anzahl an Relationen erzeugt. Wiederum werden zum Beweis der zugrundeliegenden geometrischen Aussagen Familien von Kurven betrachtet, um so die Uniformität zu gewährleisten. Beide Algorithmen wurden zudem implementiert. Zum Abschluss der Arbeit werden die Ergebnisse der entsprechenden Experimente vorgestellt und eingeordnet.

Dans cette thèse, j'étudie deux aspects distincts de la cryptographie basée sur les courbes elliptiques et hyperelliptiques. Dans une première partie, je confronte deux méthodes de calcul de couplages, originales car ne reposant pas sur le traditionnel algorithme de Miller. Ainsi, dans [42], K. Stange calcula le couplage de Tate sur une courbe elliptique à partir d'un nouvel outil, les elliptic nets. Y. Uchida et S. Uchiyama généralisèrent ces objets au cas hyperelliptique ([47]), mais ne donnèrent un algorithme pour le calcul de couplages que dans le cas des courbes de genre 2. Mon premier travail dans cette thèse fut de donner cet algorithme pour le cas général. De leur côté, D. Lubicz et D. Robert donnèrent dans [28] une autre méthode de calcul de couplage, basée sur les fonctions thêta. Le second résultat de ma thèse est de réunifier ces deux méthodes : je montre que la formule de récurrence à la base des nets est une conséquence des formules d'addition des fonctions thêta utilisées dans l'algorithme de Lubicz et Robert. Dans la seconde partie de ma thèse, je me suis intéressé à l'algorithme de calcul d'index attaquant le problème du logarithme discret sur les courbes elliptiques et hyperelliptiques. Dans le cas elliptique, une des étapes principales de cette attaque repose sur les polynômes de Semaev. Je donne une nouvelle construction ces polynômes en utilisant la fonction sigma de Weierstrass, pour pouvoir ensuite les généraliser pour la première fois au cas hyperelliptique. / In this thesis, I study two different aspects of elliptic and hyperelliptic curves based cryptography.In the first part, I confront two methods of pairings computation, whose original feature is that they are not based the traditional Miller algorithm. Therefore, in [42], K. Stange computed Tate pairings on elliptic curves using a new tool, the elliptic nets. Y. Uchida and S. Uchiyama generalized these objects to hyperelliptic case ([47]), but they gave an algorithm for pairing computation only for the genus 2 case. My first work in this thesis was to give this algorithm for the general case. Meanwhile, D. Lubicz and D. Robert gave in [28] an other pairing computation method, based on theta functions. The second result of my thesis is the reunification of these two methods : I show that the recurrence equation which is the basis of nets theory is a consequence of the addition law of theta functions used in the Lubicz and Robert’s algorithm. In the second part, I study the index calculus algorithm attacking the elliptic and hyperelliptic curve discrete logarithm problem. In the elliptic case, one of the main steps of this attack requires the Semaev polynomials. I reconstruct these polynomials using Weierstrass sigma function, with the purpose of giving their first hyperelliptic generalization.

La cryptologie consiste en l’étude des techniques utilisées par deux entités pour communiquer en secret en présence d’une troisième. Les propriétés mathématiques qui sous-tendent ces techniques garantissent que leur attaque reste infaisable en pratique par un adversaire malveillant. Ainsi, les protocoles s’appuient sur diverses hypothèses, comme la di fficulté présumée de factoriser des entiers ou de calculer le logarithme discret d’un élément arbitraire dans certains groupes. Cette thèse qui porte sur le problème du logarithme discret dans les corps finis s’articule autour de trois volets.Nous exposons les résultats théoriques associés au problème sans considération du groupe cible, détaillant ainsi les classes de complexité auxquelles il appartient ainsi que di fférentes approches pour tenter de le résoudre.L’étude du problème dans les corps finis commence en tant que telle par les corps présentant une caractéristique de petite taille relativement à l’ordre total du corps en question. Cette seconde partie résulte sur l’exposition d’un algorithme par représentation de Frobenius dont une application a aboutit au record actuel de calcul de logarithme discret en caractéristique 3.Pour les corps de moyenne ou grande caractéristiques, une autre méthode est requise. Le crible par corps de nombres (NFS) multiples obtient les complexités asymptotiques les plus basses pour un corps arbitraire. Un dernier chapitre introduit la notion de matrice presque creuse. L’élaboration d’un nouvel algorithme spécifique qui explicite le noyau d’une telle matrice facilite en pratique l’étape d’algèbre sous-jacente à toute variante de NFS. / Cryptography is the study of techniques for secure communication in the presence of third parties, also called adversaries. Such techniques are detailed in cryptosystems, explaining how to securely encode and decode messages. They are designed around computational hardness assumptions related to mathematical properties, making such algorithms hard to break in practice by any adversary. These protocols are based on the computational difficulty of various problems which often come from number theory, such as integer factorization or discrete logarithms computations. This manuscript focuses on the discrete logarithm problem in finite fields and revolves around three axes.First we detail classical results about the problem without any consideration to the target group. We deal with complexity classes and some general methods that do not need any information on the group.The study of the discrete logarithm problem in finite fields starts with small characteristic ones. The aim is to present a Frobenius representation algorithm that leads to the current discrete logarithm record in characteristic 3.For medium or large characteristics finite fields, another approach is required. The multiple number field sieve reaches the best asymptotic heuristic complexities for this double range of characteristics. We also introduce the notion of nearly sparse matrices. Designing a new algorithm dedicated to explicitly give the kernel of such a matrix eases in practice the linear algebra step of any variant of the number field sieve.

Seit W. Diffie und M. Hellman im Jahr 1976 ihren Ansatz für einen sicheren kryptographischen Schlüsselaustausch vorgestellten, ist der sogenannte Diskrete Logarithmus zu einem zentrales Thema der Kryptoanalyse geworden. Dieser stellt eine Erweiterung des bekannten Logarithmus auf beliebige endliche Gruppen dar. In der vorliegenden Dissertation werden zwei von C. Diem eingeführte Algorithmen untersucht, mit deren Hilfe der diskrete Logarithmus in der Picardgruppe glatter, nichthyperelliptischer Kurven vom Geschlecht g > 3 bzw. g > 4 über endlichen Körpern berechnet werden kann. Beide Ansätze basieren auf der sogenannten Indexkalkül-Methode und benutzen zur Erzeugung der dafür benötigten Relationen spezielle Linearsysteme, welche durch Schneiden von ebenen Modellen der Kurve mit Geraden erzeugt werden. Um Aussagen zur Laufzeit der Algorithmen tätigen zu können, werden verschiedene Sätze über die Geometrie von Kurven bewiesen. Als zentrale Aussage wird zum einem gezeigt, dass ebene Modelle niedrigen Grades effizient berechnet werden können. Zum anderen wird bewiesen, dass sich bei genügend großem Grundkörper die Anzahl der vollständig über dem Grundkörper zerfallenden Geraden wie heuristisch erwartet verhällt. Für beide Aussagen werden dabei Familien von Kurven betrachtet und diese gelten daher uniform für alle glatten, nichthyperelliptischen Kurven eines festen Geschlechts. Die genannten Resultate führen schlussendlich zu dem Beweis einer erwarteten Laufzeit von O(q^(2-2/(g-1))) für den ersten der beiden Algorithmen, wobei q die Anzahl der Elemente im Grundkörper darstellt. Der zweite Algoritmus verbessert dies auf eine heuristische Laufzeit in O(q^(2-2/(g-2))), imdem er Divisoren von höherem Spezialiätsgrad erzeugt. Es wird bewiesen, dass dieser Ansatz für einen uniform gegen 1 konvergierenden Anteil an glatten, nichthyperelliptischen Kurven eines festen Geschlechts über Grundkörpern großer Charakteristik eine große Anzahl an Relationen erzeugt. Wiederum werden zum Beweis der zugrundeliegenden geometrischen Aussagen Familien von Kurven betrachtet, um so die Uniformität zu gewährleisten. Beide Algorithmen wurden zudem implementiert. Zum Abschluss der Arbeit werden die Ergebnisse der entsprechenden Experimente vorgestellt und eingeordnet.