Title: Supporting algorithms of number field sieve Author: Adéla Skoková Department: Department of Algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc. Abstract: In this work we study the first part of the algorithm of number field sieve, generating of polynomials. At first we describe all the algorithm of the sieve for understanding of the role of polynomials and their impact on the entire algorithm. Then we present their characteristics and evaluation. The last part is about the most effective know algorithms of generating polynomials, invented by Thorsen Klinjung. The second Kleinjung algoritm was also programmed. Keywords: GNFS, Number sieve, Number field, Kleinjung algorithm Powered by TCPDF (www.tcpdf.org)

This thesis consists of two papers with somewhat different flavours. In Paper I we compute the étale cohomology ring H^*(X,Z/nZ) for X the ring of integers of a number field K. As an application, we give a non-vanishing formula for an invariant defined by Minhyong Kim. We also give examples of two distinct number fields whose rings of integers have isomorphic cohomology groups but distinct cohomology ring structures. In Paper II we define stacky building data for stacky covers in the spirit of Pardini and give an equivalence of (2, 1)-categories between the category of stacky covers and the category of stacky building data. We show that every stacky cover is a flat root stack in the sense of Olsson and Borne–Vistoli and give an intrinsic description of it as a root stack using stacky building data. When the base scheme S is defined over a field, we give a criterion for when a stacky building datum comes from a ramified cover for a finite abelian group scheme over k, generalizing a result of Biswas–Borne. / Denna avhandling består av två artiklar som skiljer sig något i karaktär. I Artikel I beräknar vi den étala kohomologiringen H^*(X,Z/nZ) då X är ringen av heltal av en talkropp K. Som en tillämpning, ger vi ett kriterium i form av en formel för när en invariant definierad av Minhyong Kim är noll eller ej. Vi ger också exempel på två olika talkroppar vars ringar av heltal har isomorfa kohomologigrupper men olika kohomologiringstrukturer. I Artikel II definierar vi stackig byggnadsdata för stackiga övertäckningar i Pardinis anda och visar en ekvivalens av (2,1)-kategorier mellan kategorin av stackiga övertäckningar och kategorin av stackig byggnadsdata. Vi visar att varje stackig övertäckning är en platt rotstack i Olsson och Borne–Vistolis mening och vi ger en intrinsisk beskrivning av den som en rotstack med hjälp av stackig byggnadsdata. När basen S är definierad över en kropp, ger vi ett kriterium för när ett stackigt byggnadsdatum kommer från en ramifierad övertäckning för ett ändligt abelskt gruppschema över k. Detta generaliserar ett resultat av Biswas–Borne.

Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 110 δεκαδικών ψηφίων είναι ο General Number Field Sieve (GNFS). Ο αλγόριθμος αυτός είναι ο καρπός πολλών ετών έρευνας, κατά τη διάρκεια της οποίας παράγονταν ολοένα και ταχύτεροι αλγόριθμοι για να καταλήξουμε μέχρι στιγμής στον αλγόριθμο GNFS. Πρωταρχικός σκοπός της παρούσης μεταπτυχιακής εργασίας είναι η παρουσίαση του θεωρητικού μαθηματικού υπόβαθρου πάνω στο οποίο βασίζεται ο GNFS καθώς και η ακολουθιακή υλοποίηση της βασικής εκδοχής του αλγορίθμου. Ως γλώσσα υλοποίησης επιλέχθηκε η C++. Η υλοποίηση έγινε σε συνεργασία με τον συμφοιτητή μου και αγαπητό φίλο Χρήστο Μπακογιάννη, όπου στα πλαίσια της μεταπτυχιακής του εργασίας πραγματοποιήθηκε η μεταφορά της ακολουθιακής υλοποίησης του αλγορίθμου σε παράλληλο κατανεμημένο περιβάλλον χρησιμοποιώντας το Message Passing Interface (MPI). Ο πηγαίος κώδικας της υλοποίησης καθώς και σχετικές πληροφορίες υπάρχουν online στη σελίδα http://kmgnfs.cti.gr. Σημειώνεται πως για την ευκολότερη και απρόσκοπτη ανάγνωση της εργασίας αυτής, ο αναγνώστης θα πρέπει να έχει ένα βαθμό εξοικείωσης με βασικές έννοιες της θεωρίας αριθμών, της αλγεβρικής θεωρίας αριθμών και της γραμμικής άλγεβρας. / Many public-key cryptosystems build their security on our inability to factor very large integers. The General Number Field Sieve (GNFS) is the most efficient, and at the same time most complex, classical known algorithm for factoring integers larger than 110 digits. This algorithm is the result of many years of research, during which, faster and faster algorithms were developed finally winding up to the development of the GNFS. The main purpose of this master thesis is the presentation of the mathematical ideas, on which the GNFS was developed, as well as a sequential implementation of the basic version of the algorithm. C++ was the language of choice. The implementation took place in collaboration with my colleague and dear friend Christos Bakogiannis, where as part of his master thesis, a distributed implementation of the algorithm using Message Passing Interface (MPI) was also developed. The source code of the implementations is publicly available and can be found online at http://kmgnfs.cti.gr. It is presumed that the reader is familiar with basic concepts of number theory, algebraic number theory and linear algebra.

Title: Solving diophantine equations by factorization in number fields Author: Bc. Maroš Hrnčiar Department: Department of Algebra Supervisor: Mgr. Vítězslav Kala, Ph.D., Mathematical Institute, University of Göttingen Abstract: The question of solvability of diophantine equations is one of the oldest mathematical problems in the history of mankind. While different approaches have been developed for solving certain types of equations, this thesis predo- minantly deals with the method of factorization over algebraic number fields. The idea behind this method is to express the equation in the form L = yn where L equals a product of typically linear factors with coefficients in a particular number field. Provided that several assumptions are met, it follows that each of the factors must be the n-th power of an element of the field. The structure of number fields plays a key role in the application of this method, hence a crucial part of the thesis presents an overview of algebraic number theory. In addition to the general theoretical part, the thesis contains all the necessary computations in specific quadratic and cubic number fields describing their basic characteristics. However, the main objective of this thesis is solving specific examples of equati- ons. For instance, in the case of equation x2 + y2 = z3 we...

<p>This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. </p><p>The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. </p><p>Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).</p>

The thesis is concerned with the theory of binary quadratic forms with coefficients in the ring of algebraic integers of a number field. Under the assumption that the number field is of narrow class number one, there is developed a theory of composition of such quadratic forms. For a given discriminant, the composition is determined by a bijection between classes of quadratic forms and a so-called relative oriented class group (a group closely related to the class group). Furthermore, Bhargava cubes are generalized to cubes with entries from the ring of algebraic integers; by using the composition of quadratic forms, the composition of Bhargava cubes is proved in the generalized case. 1

Large sparse matrices arise in many applications, especially in the major problems of Cryptography of factoring integers and computing discrete logarithms. We focus attention on such matrices called sieve matrices generated after the sieving stage of the algorithms for integer factoring. We need to solve large sparse system of equations Bx = 0, with sieve matrices B arising in this context. The traditional Gaussian elimination, with a cubic run time, is not efficient for handling such matrices. Better algorithms for such input matrices are the quadratic runtime algorithms based on Block Lanczos(BL) or Wiedemann techniques. Of these two, BL is even better for large integer factoring algorithms. We carry out an efficient implementation of the Block Lanczos algorithm for finding the vectors in the null space of the the sieve matrix. We report our test results using our implementation for matrices of sizes up to 106. We plan to use this implementation in our ongoing projects on factoring the large RSA challenge integers of sizes 640 bits(called RSA-640) and beyond. So it is useful to exploit possible parallelism. We propose a scheme for parallelizing certain steps of the Block Lanczos method, taking advantage of structural properties of the sieve matrix. The sizes of matrices arising in integer factoring context are quite large. Hence we also discuss some techniques that are used to reduce the size of the sieve matrix. We also consider the last stage of the NFS Algorithm for finding square roots of large algebraic numbers and outline a sketch of our algorithm.

Disertaciją sudaro darbai, autoriaus atlikti 2006-2013 metais. Šiuos darbus jungianti tema yra algebrinių kreivių, apibrėžtų virš racionaliųjų skaičių, šeimos, einančios per taškus, kurių koordinatės priklauso duotam skaičių kūnui ar jo sveikųjų skaičių žiedui. Pirmoje disertacijos dalyje yra gaunama vidutinio mažo aukščio racionaliųjų taškų kiekio ant fiksuoto žanro hiperelipsinių kreivių asimptotika. Antroje dalyje šis rezultatas išplečiamas, apibūdinant vidutinį homogeninių daugianarių reikšmių taškuose, kurių koordinatės yra mažo aukščio tarpusavyje pirminiai skaičiai, sutampančių su duoto vieno kintamojo daugianario reikšmėmis sveikuosiuose taškuose, skaičių. Trečioje dalyje sukonstruojamos nedidelės kreivių, apibrėžtų virš racionaliųjų skaičių ir išvengiančių taškų, kurių koordinatės priklauso duotam skaičių kūnui, šeimos. Ketvirtoje dalyje nagrinėjamos kongruenčių skaičių kreivės. Įrodoma, kad bent pusė pirminių skaičių p, kurie lieka inertiški cikliniame skaičių kūne K, atitinka kreives 16p^2 = x^4 - y^2, neturinčias netrivialių taškų su koordinatėmis to kūno sveikųjų skaičių žiede. Paskutinėje dalyje iliustruojamas Gauso sveikųjų skaičių skaidymosi daugikliais vienatinumo taikymas įrodant, kad konkreti hiperelipsinė kreivė neturi taškų su sveikosiomis koordinatėmis. / In this document, the author collected his work that ranges through the years 2006-2013. The common theme that occurs in its five separate parts is that of families of algebraic curves defined over the rational numbers with points over a number field or over its ring of integers. In the first part, average number of rational points of small height on hyperelliptic curves of fixed genus is described. In the second part, this result is extended to describing how often, on average, values of homogeneous polynomials at pairs of small coprime integers are values of a given univariate polynomial with integer coefficients. Further, small families of curves that are defined over the rational numbers and do not have points over a given number field are constructed. In the subsequent part, congruent number curves are investigated. It is shown that, given a cyclic number field K, at least half of the prime numbers p that remain inert in K correspond to curves 16p^2 = x^4 - y^2 that do not have nontrivial points over the ring of integers of K. In the last part, a short exposition to a classical technique of showing that a particular curve does not have integral points is given.

In this document, the author collected his work that ranges through the years 2006 - 2013. The common theme that occurs in its five parts is that of families of algebraic curves defined over the rational numbers with points over a number field or over its ring of integers. In the first part, average number of rational points of small height on hyperelliptic curves of fixed genus is described. In the second part, this result is extended to describing how often, on average, values of homogeneous polynomials at pairs of small coprime integers are values of a given univariate polynomial with integer coefficients. Further, small families of curves that are defined over the rational numbers and do not have points over a given number field are constructed. In the subsequent part, congruent number curves are investigated. It is shown that, given a cyclic number field K, at least half of the prime numbers p that remain inert in K correspond to curves 16p^2 = x^4 - y^2 that do not have nontrivial points over the ring of integers of K. In the last part, a short exposition to a classical technique of showing that a particular curve does not have integral points is given. / Disertaciją sudaro darbai, autoriaus atlikti 2006-2013 metais. Šiuos darbus jungianti tema yra algebrinių kreivių, apibrėžtų virš racionaliųjų skaičių, šeimos, einančios per taškus, kurių koordinatės priklauso duotam skaičių kūnui ar jo sveikųjų skaičių žiedui. Pirmoje disertacijos dalyje yra gaunama vidutinio mažo aukščio racionaliųjų taškų kiekio ant fiksuoto žanro hiperelipsinių kreivių asimptotika. Antroje dalyje šis rezultatas išplečiamas, apibūdinant vidutinį homogeninių daugianarių reikšmių taškuose, kurių koordinatės yra mažo aukščio tarpusavyje pirminiai skaičiai, sutampančių su duoto vieno kintamojo daugianario reikšmėmis sveikuosiuose taškuose, skaičių. Trečioje dalyje sukonstruojamos nedidelės kreivių, apibrėžtų virš racionaliųjų skaičių ir išvengiančių taškų, kurių koordinatės priklauso duotam skaičių kūnui, šeimos. Ketvirtoje dalyje nagrinėjamos kongruenčių skaičių kreivės. Įrodoma, kad bent pusė pirminių skaičių p, kurie lieka inertiški cikliniame skaičių kūne K, atitinka kreives 16p^2 = x^4 - y^2, neturinčias netrivialių taškų su koordinatėmis to kūno sveikųjų skaičių žiede. Paskutinėje dalyje iliustruojamas Gauso sveikųjų skaičių skaidymosi daugikliais vienatinumo taikymas įrodant, kad konkreti hiperelipsinė kreivė neturi taškų su sveikosiomis koordinatėmis.

This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).