Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues. The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03]. They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem. This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP⁺05] that require even less bandwidth. In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented. Finally, we list some open research problems.

Communicating bits over a network is expensive. Therefore, cryptosystems that transmit as little data as possible are valuable. This thesis studies several cryptosystems that require significantly less bandwidth than conventional analogues. The systems we study, called torus-based cryptosystems, were analyzed by Karl Rubin and Alice Silverberg in 2003 [RS03]. They interpreted the XTR [LV00] and LUC [SL93] cryptosystems in terms of quotients of algebraic tori and birational parameterizations, and they also presented CEILIDH, a new torus-based cryptosystem. This thesis introduces the geometry of algebraic tori, uses it to explain the XTR, LUC, and CEILIDH cryptosystems, and presents torus-based extensions of van Dijk, Woodruff, et al. [vDW04, vDGP⁺05] that require even less bandwidth. In addition, a new algorithm of Granger and Vercauteren [GV05] that attacks the security of torus-based cryptosystems is presented. Finally, we list some open research problems.

Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-09-04T15:09:18Z No. of bitstreams: 1 arquivototal.pdf: 1305751 bytes, checksum: e328135f0399052c0b94303d6ed26e2d (MD5) / Approved for entry into archive by Viviane Lima da Cunha (viviane@biblioteca.ufpb.br) on 2017-09-04T15:54:43Z (GMT) No. of bitstreams: 1 arquivototal.pdf: 1305751 bytes, checksum: e328135f0399052c0b94303d6ed26e2d (MD5) / Made available in DSpace on 2017-09-04T15:54:43Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1305751 bytes, checksum: e328135f0399052c0b94303d6ed26e2d (MD5) Previous issue date: 2017-01-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The Euler's Number, denoted by e and corresponding to the base of the Natural Logarithms, despite being one of the most important constants in Mathematics, both by the variety of its mathematical implications and by the number of its practical applications, remains unknown to many people. It is common to nd Engineering or even Exact Sciences students who only became aware of the existence of e after taking a Calculus Course. It is also not di cult to nd students who, even after such contact, seem to never realize the importance of this number. The e is a versatile constant. Although, in general, it appears related to results involving Di erential and Integral Calculus, it is present in several problems of di erent Mathematics areas. We can nd it, besides Analysis and Function Theory, in Financial Mathematics, Combinatorial Analysis, Probability, Trigonometry, Geometry, Statistics, Number Theory. In this work, we make a brief historical analysis about the discovery of the Euler's Number, we present its de nition, as well as alternative ways of characterizing it through in nite sums and products. We also address two interesting problems in which it is present: the counting of the number of partitions of a nite non-empty set and obtaining an approximation for the factorial of a natural number, in which we nd the Stirling's Approximation. / O Número de Euler, denotado por e e correspondente à base dos Logaritmos Naturais, apesar de ser uma das constantes mais importantes da Matemática, tanto pela variedade de suas implicações matemáticas quanto pela quantidade de suas aplicações práticas, permanece desconhecido por muitos. É comum encontrarmos estudantes de Engenharia, ou até mesmo das Ciências Exatas, que só tomaram conhecimento da existência do e após um curso de Cálculo. Também não é difícil nos depararmos com alunos que, mesmo após tal contato, parecem nunca terem percebido a importância desse número. O e é uma constante versátil. Apesar de, em geral, aparecer relacionado a resultados envolvendo o Cálculo Diferencial e Integral, ele se faz presente em diversos problemas de diferentes áreas da Matemática. Podemos encontrá-lo, além da Análise e Teoria de Funções, na Matemática Financeira, na Análise Combinatória, na Probabilidade, na Trigonometria, na Geometria, na Estatística, na Teoria dos Números. Neste trabalho, realizamos uma breve análise histórica sobre o descobrimento do Número de Euler, exibimos sua de nição, além de formas alternativas de caracterizá-lo através de somas e produtos in nitos, e abordamos dois interessantes problemas nos quais ele se faz presente: o da contagem do número de partições de um conjunto não vazio nito e o da obtenção de uma aproximação para o fatorial de um número natural, no qual nos deparamos com a Fórmula de Stirling.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-02-19T16:24:23Z No. of bitstreams: 1 ulissesdossantosborges.pdf: 1138379 bytes, checksum: a36ee974ac00a183ccc63f70893ab91f (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-02-26T13:51:12Z (GMT) No. of bitstreams: 1 ulissesdossantosborges.pdf: 1138379 bytes, checksum: a36ee974ac00a183ccc63f70893ab91f (MD5) / Made available in DSpace on 2016-02-26T13:51:12Z (GMT). No. of bitstreams: 1 ulissesdossantosborges.pdf: 1138379 bytes, checksum: a36ee974ac00a183ccc63f70893ab91f (MD5) Previous issue date: 2014-06-06 / Neste trabalho pretende-se abordar o ensino de logaritmos e das funções exponenciais e logarítmicas por meio de modelos matemáticos que os caracterizam. Faremos uso das progressões aritméticas e geométricas como pontos importantes no entendimento das funções exponenciais e logarítmicas. E, recomendamos, antes de iniciar o estudo destas funções, fazer um breve estudo daquelas progressões; visto esta ordem não ser comun no Ensino Médio. Por meio de situações problemas, onde a função logarítmica e a sua inversa, a função exponencial, se mostram os modelos matemáticos mais adequados, devido as suas caracterizações, procuraremos mostrar as principais características, propriedades e definições dessas duas funções. Estas situações problemas serão dadas em atividades propostas onde pretendemos mostrar o desenvolvimento dos conceitos e propriedades dos logaritmos no decorrer do tempo, exemplificar a caracterização da função logarítmica e da função exponencial e apresentar exemplos de problemas do cotidiano que são modelados por essas funções. Faremos uso, também, de uma planilha eletrônica, em uma das atividades propostas, para mostrar propriedades das funções exponenciais e logarítmicas e a importante constante matemática e, que aparece naturalmente em fenômenos da Natureza. Veremos que a razão inicial do sucesso dos logaritmos, aumentar o poder de computação, perdeu este lugar, nos dias de hoje, para os computadores e as máquinas de calcular. Atualmente, o motivo que fazem com que os logaritmos continuem a merecer destaque no ensino de Matemática é porque a função logarítmica e a função exponencial constituem a única maneira de descrever matematicamente uma grandeza cuja taxa de variação é proporcional à quantidade daquela grandeza presente num dado instante. / This work intends to address the teaching of logarithms and exponential and logarithmic functions by means of mathematical models that characterize them. We will use the arithmetic and geometric progressions as main points in understanding of exponential and logarithmic functions. We also recommend that before starting the study of these functions, make a brief study of those progressions, since this order may not be common in High School. Through problem situations, where the logarithmic function and its inverse, the exponential function, it is shown the most appropriate mathematical models, due to its specifications, we will show the main features, properties and definitions of these two functions. These problem situations will be given in proposed activities where we intend to show the development of the concepts and the logarithms properties in the course of time, exemplify the characterization of the logarithmic function and the exponential function and provide examples of everyday problems that are modeled by these functions. We will also use a spreadsheet, in one of the proposed activities, to show properties of the exponential and logarithmic functions and the important mathematical constant "e", which usually appears in natural phenomena. We will see that the initial reason of logarithms success, to increase computing power, lost ground nowadays, for computers and calculators. Currently, the reason that makes the logarithms continue to receive emphasis on the teaching of Mathematics is because the logarithmic function and the exponential function is the only way to describe the magnitude mathematically whose rate of variation is proportional to the quantity of that magnitude in a given moment.

Cette thèse comporte trois volets indépendants en cryptographie, en théorie de Hodge p-adique et en analyse numérique.La première partie consiste en l'étude d'algorithmes performants de résolution du logarithme discret. La résolution du logarithme discret consiste à déterminer les exposants d'une famille fixée de générateurs dans la décomposition des éléments du groupe. Dans le cas des groupes multiplicatifs d'un corps fini, la complexité des calculs dépendent de la taille - dite de petite, moyenne ou grande caractéristique- de la caractéristique du corps dans lesquels on effectue les calculs.Nous présentons différents algorithmes dans chacune des caractéristiques (petite, moyenne ou grande) en précisant quel est l'algorithme le plus performant dans chacun des cas.La seconde partie s'inscrit dans le contexte du programme de Langlands p-adique. Nous présentons une généralisation de l'un des outils centraux de la théorie, les modules de Breuil-Kisin, en plusieurs variables La troisième partie est un travail effectué en collaboration avec Victor Vilaça Da Rocha, Roberta Tittarelli, Richard Sambilason Rafefimanana, Victor Michel-Dansac et Benjamin Couéraud. Il a été initié lors de la treizième SEME, Semaine d'Etudes Maths Entreprises organisée par l'Agence pour les Mathématiques en Interaction avec l'Entreprise et la Société (AMIES).L'Institut Français du Pétrole et des Energies Nouvelles nous a soumis un problème de résolution numérique d'un système d'équations modélisant la désorption d'un gaz de schiste en une dimension.Nous proposons plusieurs schémas du premier ordre recourant à un traitement implicite de l'équation de relaxation. Enfin nous présentons un schéma numérique d'ordre deux en temps. / In this thesis, we present three independent works in cryptography, p-adic Hodge theory and Numerical analysis.First we present several algorithms to solve the discrete logarithm in several characteristic finite fields. We are particularly interested with the determination of classes of polynomial functions with small coefficients.The second part of the thesis deals with one of the major object of p-adic Hodge theory. We present a multi-variable version of Breuil-Kisin modules where the Lubin-Tate tower replaces the classical cyclotomic tower. He third proposes two numerical schemes for the modelisation of desorption of shale gaz.

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.

Le problème du logarithme discret est une brique fondamentale de nombreux protocoles de communication sécurisée. Son instantiation sur les courbes elliptiques a permis, grâce à la petite taille des opérandes considérées, le déploiement de primitives asymétriques efficaces sur des systèmes embarqués. De nos jours, les cryptosystèmes utilisant des courbes elliptiques, aussi appelées courbes de genre 1, sont déjà intensément utilisés: il est donc impératif de savoir estimer précisément la robustesse de ces systèmes. L'existence d'attaques mathématiques permettant de transférer un problème de logarithme discret elliptique dans un autre type de courbe algébrique, et la nouvelle compétitivité des courbes de genre 2 imposent de ne pas se restreindre à la seule compréhension du problème sur les courbes elliptiques.Dans cette optique, le sujet de cette thèse se concentre sur les attaques algébriques sur les courbes de genre supérieur à 1. Les algorithmes de type calcul d'indice sont en général préférés pour ce genre d'attaque. Ces algorithmes se déroulent en deux phases: la première, appelée phase de récolte, dispose de nombreuses modélisations algébriques dépendant de la courbe ciblée. Le problème sous-jacent revient à savoir décomposer efficacement des points dans la variété Jacobienne de la courbe en somme d'autres points.On propose dans un premier temps une approche par crible pour la phase de récolte, s'adaptant à tous les types de courbes de genre plus grand que 1, et qui est expérimentalement plus efficaces que les méthodes de l'état de l'art. Cette méthode a l'avantage de proposer une implémentation immédiate, et évite les problèmes usuels de gestion des relations obtenues.Ensuite, on se concentre les variantes de calcul d'indice appelées attaques par décomposition, et ciblant les courbes définies sur des extensions de corps. Dans cette situation, la phase de récolte est effectuée par résolution de nombreux systèmes polynomiaux multivariés. On propose une nouvelle approche de modélisation de ces systèmes, en généralisant la notion de polynômes de sommation elliptique à tout les types de courbes algébriques. Pour cela on fait appel à la théorie de l'élimination, tandis que l'aspect pratique est gérée par des méthodes de bases de Gröbner.Enfin, on fournit des algorithmes d'amélioration du processus de résolution des systèmes lorsque la caractéristique du corps de base est paire. Par le biais d'une présentation théorique générale et en utilisant des méthodes de bases de Gröbner, on propose une analyse fine de l'impact de ces améliorations sur la complexité de la résolution. Cette analyse fine, ainsi qu'une implémentation dédiée, nous permettent d'attaquer une courbe de genre 2 satisfaisant des bornes de sécurité réaliste en pratique. / The discrete logarithm problem is a fundamental brick for several protocols for secured communications. Its instantiation over elliptic curves allows the deployment of efficient asymmetric primitives in embedded systems, because of the small size of the parameters considered. Nowadays, elliptic curves cryptosystems are already widely used: it is therefore crucial to precisely understand the hardness of such systems. Because of the existence of mathematical attacks enabling the transfer from an elliptic curve discrete logarithm problem to another algebraic curve, and the upcoming competitivity of genus 2 curves, it is mandatory to study the problem not only for elliptic curves, but for the other curves as well.In this way, this thesis focuses on the algebraic attacks over curves with genus greater than 1. The index calculus family of algorithms is in general preferred for this kind of attacks. Those algorithms run in two phases: the first, called harvesting phase, can be modelled by different algebraic approaches, depending in the targetted curve. The underlying problem amounts to knowing how to decompose efficiently points in the Jacobian variety of the curve into sums of other points.First, we propose a sieving approach to the harvesting, that can be adated to any type of curves with genus greater than 1, and which turns to be experimentally more efficient than state-of-the-art's methods. Moreover, our method allows a close-to-immediate implementation, and avoid complications coming from relations management.Our second focus is on a variant of index calculus called decomposition attack, targetting curves defined over field extensions. In this situation, harvesting is done by solving numerous multivariate polynomial systems. We propose a new approach to this modelling by generalizing the notion of elliptic summation polynomias to any type of algebraic curves. This uses elimination theory, and the computational aspect is handled by Gröbner bases methods.Third, we give algorithms to improve the solving process of the systems arising from a decomposition attacks when the characteristic of the base field is even. By mean of a general theoretical presentation, and using Gröbner bases methods, we give a sharp analysis of the impact of such improvement on the complexity of the resolution process. This sharp analysis together with a dedicated implementation allows us to attack a genus 2 curve satisfying realistic security parameters.

This master thesis is about Elliptic Curve Digital Signature Algorithm or ECDSA and two of the known attacks on this security system. The purpose of this thesis is to find points that are likely to be points of high order on an elliptic curve. If we have a point P of high order and if Q = mP, then we have a large set of possible values of m. Therefore it is hard to solve the Elliptic Curve Discrete Logarithm Problem or ECDLP. We have investigated on the time of finding the solution of ECDLP for a certain amount of elliptic curves based on the order of the point which is used to create the digital signatures by those elliptic curves. Method: Algebraic Structure of elliptic curves over finite fields and Discrete logarithms. This has been done by two types of attacks namely Baby Step, Giant Step and Pollard’s Rho and all of the programming parts has been done by means of Mathematica. Conclusion: We have come into a conclusion of having the probable good points which are the points of high order on elliptic curves through the mentioned attacks in which solving the ECDLP is harder if these points have been used in generating the digital signature. These probable good points can be estimated by means of a function we have come up with. The input of this function is the order of the point and the output is the time of finding the answer of ECDLP.

Cryptosystems based on elliptic curves are in wide-spread use, they are considered secure because of the difficulty to solve the elliptic curve discrete logarithm problem. Pollard's rho method is regarded as the best method for attacking the logarithm problem to date, yet it is still not efficient enough to break an elliptic curve cryptosystem. This is because its time complexity is O(√n) and for uses in cryptography the value of n will be very large. The objective of this thesis is to see if there are ways to improve Pollard's rho method. To do this, we study some modifications of the original functions used in the method. We also investigate some different functions proposed by other researchers to see if we can find a version that will improve the performance. From the experiments conducted on these modifications and functions, we can conclude that we get an improvement in the performance for some of them.

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)