Nous affinons le crible asymptotique de Bombieri afin d’obtenir un asymptotique en variables localisées. Comme conséquence, nous démontrons, sous la conjecture d’Elliott-Halberstam, qu’il existe une infinité de nombres presque premiers jumeaux, c’est à dire tels que pour tout ε > 0, p est premier et p−2 est soit premier, soit de la forme p1p2 où p1 < Xε, et nous en donnons un asymptotique. A ce travail s’ajoutent deux chapitres : d’un côté, une preuve montrant comment une méthode sans crible préliminaire donne un résultat plus faible en nécessitant une hypothèse plus forte, ce qui nous permettra de détailler plusieurs estimations et de souligner l’intérêt de notre approche. D’un autre côté une exposition pédagogique d’une méthode donnant un accès facile et explicite à plusieurs estimations de moyennes de fonctions multiplicatives. / We improve Bombieri’s asymptotic sieve to localise the variables. As a consequence, we prove, under a Elliott-Halberstam conjecture, that there exists an infinity of twins almost prime. Those are prime numbers p such that for all ε > 0, p −2 is either a prime number or can be written as p1p2 where p1 and p2 are prime and p1 < Xε, and we give the explicit asymptotic. In addition to this main work, there are two other chapters: the first one gives an asymptotic of prime numbers p such p−2is either a prime number or a product of three primes without using a preliminary sieve and so a stronger conjecture was needed. Hence this part shows the strength of the preliminary sieve and presents a few detailed sommations, most of them involving the Möbius fonction, that could be useful. The second one presents an easy and explicit method to calculate an average order of multiplicative functions.

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

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)

Background. Prime numbers are integers divisible only on 1 and themselves, and one of the oldest methods of finding them is through a process known as sieving. A prime number sieving algorithm produces every prime number in a span, usually from the number 2 up to a given number n. In this thesis, we will cover the three sieves of Eratosthenes, Sundaram, and Atkin. Objectives. We shall compare their sequential CPU implementations to their parallel GPGPU (General Purpose Graphics Processing Unit) counterparts on the matter of performance, accuracy, and suitability. GPGPU is a method in which one utilizes hardware indented for graphics rendering to achieve a high degree of parallelism. Our goal is to establish if GPGPU sieving can be more effective than the sequential way, which is currently commonplace.   Method. We utilize the C++ and CUDA programming languages to implement the algorithms, and then extract data regarding their execution time and accuracy. Experiments are set up and run at several sieving limits, with the upper bound set by the memory capacity of available GPU hardware. Furthermore, we study each sieve to identify what characteristics make them fit or unfit for a GPGPU approach. Results. Our results show that the sieve of Eratosthenes is slow and ill-suited for GPGPU computing, that the sieve of Sundaram is both efficient and fit for parallelization, and that the sieve of Atkin is the fastest but suffers from imperfect accuracy.   Conclusions. Finally, we address how the lesser concurrent memory capacity available for GPGPU limits the ranges that can be sieved, as compared to CPU. Utilizing the beneficial characteristics of the sieve of Sundaram, we propose a batch-divided implementation that would allow the GPGPU sieve to cover an equal range of numbers as any of the CPU variants.

An experimental pressure swing adsorption unit has been constructed and used to investigate the separation of carbon dioxide from carbon dioxide enriched air using both an activated carbon and a type 5A molecular sieve adsorbent. Continuous, cyclic operation was achievedusing a pair of fixed bed adsorbers. At any one time the feed gas entered one bed at a high pressure and part of the purified gas was returned to the other bed at a reduced pressure to provide countercurrent regeneration of the adsorbent. The beds of adsorbent used were each nominally 0.165m diameter and Im. deep. Separations were carried out at approximately ambient temperature using air flow rates in the range 0.15 to 0.95 kg/m2s and inlet carbon dioxide concentrations'in the range 0.1 to 1.5% v/v. Adsorption pressures of 2 to 6.4 bar were examined, the desorption pressure being maintained throughout at essentially 1.0 bar. The period time was varied from 30 to 900 seconds and the revert ratio (i. e. the ratio of the product gas returned for desorption to the total feed rate to the unit) was varied from 0 to 1.0. The carbon dioxide separation efficiency was found to increase markedly as the adsorption pressure and the revert ratio were increased whereas it was relatively insensitive to variations in feed rate and, more particularly, feed concentration. The performance of the molecular sieve adsorbent was found to be very sensitive to the presence of moisture in the feed gas. In contrast the carbon dioxide efficiencies observed with Lhe activated carbon were unaffected by the presence of small amounts (circa 100 ppm) of moisture in the feed. A theoretical model has been proposed for predicting the performance of pressure swing adsorption systems of the type investigated and approximate analytical equations and more precise numerical techniques have been established to represent its solution. The approximate analytical solutions were found to give close agreement with the more precise methods examined under conditions corresponding to low values of a dimensionless period time parameter. The proposed theoretical model incorporates an effective irean mass transfer coefficient to represent the diffusion process within the adsorbent particles. Methods for estimation of the value of this coefficient based on the limiting conditions of a periodic constant surface flux or a periodic constant surface concentration are presented. The experimental performance data were analysed in terms of the proposed analytical solution to give values of the apparent solid phase mass transfer coefficient for comparison with those predicted theoretically. In general the apparent experimental values were consistently less than the predicted values. In addition the relationship between the experimental and predicted coefficients was found to be dependent on both the nature of the adsorbent and a parameter formed by the product of the revert ratio and the adsorption to desorption pressure ratio. Empirical correlating equations which incorporate this dependence are presented.

No description available.

No description available.

No description available.

In this thesis, we investigate in detail, certain important problems in cryptography and coding theory. In the first part of this thesis, we discuss the number field sieve and compare the two ways in which the sieving step is implemented -one method using the line sieve and the other using the lattice sieve. We discuss why the lattice sieve performs better than the line sieve in the presence of large primes -this has not been attempted before. In the second part of this thesis, we design low-correlation CDMA sequences over the Quadrature Amplitude Modulation (QAM) alphabet. The sequences proposed in this thesis have the lowest value of the maximum correlation parameter as compared to any other family in the literature. In the third part of this thesis, we design large families of optimal two-dimensional optical orthogonal codes for optical CDMA. The size of these codes is larger than any other code in the literature.

Πολλά κρυπτογραφικά σχήματα δημόσιου κλειδιού βασίζονται στο γεγονός ότι είναι υπολογιστικά δύσκολο να παραγοντοποιήσουμε μεγάλους ακέραιους αριθμούς. Ο ταχύτερος, και ταυτόχρονα πολυπλοκότερος, κλασσικός αλγόριθμος που είναι γνωστός μέχρι σήμερα για την παραγοντοποίηση ακεραίων μήκους άνω των 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.