We show the existence of a basis for a vector space over a number field with two key properties. First, the n-th basis vector has a small twisted height which is bounded above by a quantity involving the n-th successive minima associated with the twisted height. Second, at each place v of the number field, the images of the basis vectors under the automorphism associated with the twisted height satisfy near-orthogonality conditions analagous to those introduced by Korkin and Zolotarev in the classical Geometry of Numbers. Using this basis, we bound the Mahler product associated with the twisted height. This is the product of a successive minimum of a twisted height with the corresponding successive minimum of its dual twisted height. Previous work by Roy and Thunder in [12] showed that the Mahler product was bounded above by a quantity which grows exponentially as the dimension of the vector space increases. In this work, we demonstrate an upper bound that exhibits polynomial growth as the dimension of the vector space increases. / text

We conduct a parallel Hunter search in order to find a degree 7 number field K ramified at primes q and p with discriminant d(K)=q^6 p^2 where q=11 and 2

No description available.

Title: Generating polynomials for number field sieve Author: Anežka Pejlová Department: Department of Algebra Supervisor: prof. RNDr. Aleš Drápal, CSc., DSc., Department of Algebra Abstract: The topic of this thesis is mainly focused on Kleinjung algorithm for generating polynomials within the General Number Field Sieve, which is the most efficient factorization algorithm nowadays. Commonly used consecu- tions are explained with respect to the fact whether they can be rigorously proven or they are based only on heuristic assumptions. Another contribution of this thesis is the attached implementation of Kleinjung algorithm develo- ped as a part of the Number Field Sieve project led by the Department of Algebra. The appropriateness of some heuristics used in the theory beyond the Kleinjung algorithm is supported by empirical data obtained from this implementation. Keywords: Number field sieve, Kleinjung algorithm

No description available.

<p> In his monograph [Ne], Nekovar studies cohomological invariants of big Galois representations and looks at the variations of Selmer groups attached to intermediate number fields in a commutative p-adic Lie extension. In view of the formulation of the "main conjecture" for noncommutative extensions, it seems natural to extend the theory to a noncommutative p-adic Lie extension. This thesis will serve as a first step in an extension of this theory, namely, we will develop duality theorems over a noncommutative p-adic Lie extension which are extensions of Tate local duality, Poitou-Tate global duality and Grothendieck duality. </p> / Thesis / Doctor of Philosophy (PhD)

With the proliferation of computers into homes and businesses and the explosive growth rate of the Internet, the ability to conduct secure electronic communications and transactions has become an issue of vital concern. One of the most prominent systems for securing electronic information, known as RSA, relies upon the fact that it is computationally difficult to factor a "large" integer into its component prime integers. If an efficient algorithm is developed that can factor any arbitrarily large integer in a "reasonable" amount of time, the security value of the RSA system would be nullified. The General Number Field Sieve algorithm is the fastest known method for factoring large integers. Research and development of this algorithm within the past five years has facilitated factorizations of integers that were once speculated to require thousands of years of supercomputer time to accomplish. While this method has many unexplored features that merit further research, the complexity of the algorithm prevents almost anyone but an expert from investigating its behavior. We address this concern by first pulling together much of the background information necessary to understand the concepts that are central in the General Number Field Sieve. These concepts are woven together into a cohesive presentation that details each theory while clearly describing how a particular theory fits into the algorithm. Formal proofs from existing literature are recast and illuminated to clarify their inner-workings and the role they play in the whole process. We also present a complete, detailed example of a factorization achieved with the General Number Field Sieve in order to concretize the concepts that are outlined. / Master of Science

Η διείσδυση των υπολογιστών, τόσο στα σπίτια μας, όσο και κυρίως στις επιχειρήσεις, κατά τα τελευταία χρόνια, καθώς επίσης και ο συνεχώς αυξανόμενος ρυθμός χρήσης του διαδικτύου, έχουν καταστήσει την ανάγκη για ασφαλείς ηλεκτρονικές επικοινωνίες και συναλλαγές κάτι παραπάνω από επιτακτική. Ένα από τα κυρίαρχα, σήμερα, συστήματα ασφαλούς ανταλλαγής δεδομένων είναι ο αλγόριθμος RSA, η ασφάλεια του οποίου βασίζεται στο γεγονός ότι είναι πολύ δύσκολο να παραγοντοποιήσουμε έναν «μεγάλο» αριθμό στους πρώτους παράγοντές του. Ο RSA αλγόριθμος θεωρείται αρκετά ασφαλής, αν βέβαια χρησιμοποιούμε κατάλληλο, για τα σημερινά δεδομένα, μέγεθος κλειδιού. Παρόλα αυτά, σε περίπτωση που βρεθεί κάποιος αποδοτικός αλγόριθμος που να μπορεί σε «λογικό» χρόνο να παραγοντοποιήσει οποιονδήποτε μεγάλο ακέραιο, τότε αυτομάτως η ασφάλεια του αλγορίθμου αυτού έχει παραβιαστεί και θα πρέπει να στραφούμε σε εναλλακτικές μεθόδους προστασίας της πληροφορίας. Ο πιο αποδοτικός σήμερα αλγόριθμος παραγοντοποίησης μεγάλων ακεραίων είναι ο Number Field Sieve. Η έρευνα που έχει γίνει πάνω σε αυτόν τον αλγόριθμο, έχει οδηγήσει σε σημαντική πρόοδο και έχει καταστήσει, πλέον, εφικτή την παραγοντοποίηση ακεραίων που υπό άλλες προϋποθέσεις θα απαιτούσε χιλιάδες χρόνια από cpu time σε supercomputers. Αν και ακόμη και σήμερα υπάρχουν αρκετά σημεία που θα μπορούσαν να βελτιωθούν στον αλγόριθμο, κάνοντάς τον ακόμη πιο αποδοτικό, ωστόσο η πολυπλοκότητά του αποτρέπει αρκετούς να ασχοληθούν με την βελτίωσή του. Με την εργασία αυτή θα προσπαθήσουμε αρχικά να διασαφηνίσουμε όλες τις πληροφορίες που απαιτούνται για την σωστή κατανόηση της λειτουργίας του αλγορίθμου. Θα γίνει λεπτομερής περιγραφή των διαφόρων βημάτων του αλγορίθμου και θα δοθεί αναλυτικό παράδειγμα παραγοντοποίησης. Τέλος, θα παρουσιαστεί η παράλληλη υλοποίησή του αλγορίθμου, η οποία μπορεί να εκτελεστεί τόσο σε supercomputer, όσο και σε cluster υπολογιστών που επικοινωνούν μεταξύ τους με χρήση του MPI. / The recent advances in computer science, in combination with the proliferation of computers in home and businesses and the explosive growth rate of the internet transactions, have increased the needs for secure electronic communications. One of the dominant systems of secure data transactions is the RSA algorithm. RSA’ s security relies on the fact that it is computationally difficult to factor a “large” integer into its component prime integers. RSA is considered secure as long as we use proper key length. However, if an efficient algorithm is developed that can factor any arbitrarily large integer in a “reasonable” amount of time, then the whole security of the algorithm will be broken, and we will have to use alternative methods to secure our systems. Today, the fastest known method for factoring large integers is the General Number Field Sieve algorithm. Research and development of the algorithm has enabled the factorization of integers that were once thought to require thousands of years of CPU time to accomplish. While there are still many possible optimizations that could increase the algorithm’s efficiency, however the complexity of the algorithm prevents many researchers from attempting to improve it. In this master thesis we present the information needed to understand the principles upon which the algorithm is based. The discrete steps of the algorithm are described in full detail, as well as a detailed factorization example, in order to enlighten the way each step works. Finally a parallel implementation is presented, able to be executed on a supercomputer or a computer cluster, with the use of MPI.

Many of today's cryptographic systems are based on the discrete logarithm problem, e.g. the Diffie-Hellman protocol. The number field sieve algorithm (NFS) is the algorithm solving the problem of factorization of integers, but latest works show, it can be also applied to the discrete logarithm problem. In this work, we study the number field sieve algorithm for discrete logarithm and we also compare the NFS for discrete logarithm with the NFS for factoriza- tion. Even though these NFS algorithms are based on the same principle, many differences are found. 1

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. Keywords: GNFS, Number sieve, Number field, Kleinjung algorithm