Dissertations / Theses on the topic 'Primality test'

From the time of the Greeks, primality testing and factoring have fascinated mathematicians, and for centuries following the Greeks primality testing and factorization were pursued by enthusiasts and professional mathematicians for their intrisic value. There was little practical application. One example application was to determine whether or not the Fermat numbers, that is, numbers of the form F;, = 2'" + 1 were prime. Fermat conjectured that for all n they were prime. For n = 1,2,3,4, the Fermat numbers are prime, but Euler showed that F; was not prime and to date no F,, n 2 5 has been found to be prime. Thus, for nearly 2000 years primality testing and factorization was largely pure mathematics. This all changed in the mid 1970's with the advent of public key cryptography. Large prime numbers are used in generating keys in many public key cryptosystems and the security of many of these cryptosystems depends on the difficulty of factoring numbers with large prime factors. Thus, the race was on to develop new algorithms to determine the primality or otherwise of a given large integer and to determine the factors of given large integers. The development of such algorithms continues today. This thesis develops both of these themes. The first part of this thesis deals with primality testing and after a brief introduction to primality testing a new probabilistic primality algorithm, ALI, is introduced. It is analysed in detail and compared to Fermat and Miller-Rabin primality tests. It is shown that the ALI algorithm is more efficient than the Miller-Rabin algorithm in some aspects. The second part of the thesis deals with factoring and after looking closely at various types of algorithms a new algorithm, RAK, is presented. It is analysed in detail and compared with Fermat factorization. The RAK algorithm is shown to be significantly more efficient than the Fermat factoring algorithm. A number of enhancements is made to the basic RAK algorithm in order to improve its performance. The RAK algorithm with its enhancements is known as IMPROVEDRAK. In conjunction with this work on factorization an improvement to Shor's factoring algorithm is presented. For many integers Shor's algorithm uses a quantum computer multiple times to factor a composite number into its prime factors. It is shown that Shor's alorithm can be modified in a way such that the use of a quantum computer is required just once. The common thread throughout this thesis is the application of factoring and primality testing techniques to integer types which commonly occur in public key cryptosystems. Thus, this thesis contributes not only in the area of pure mathematics but also in the very contemporary area of cryptology.

La tesi presenta l'algoritmo AKS, deterministico e polinomiale, scoperto dai matematici Agrawal, Kayal e Saxena nel 2002. Esso si basa su una generalizzazione del Piccolo Teorema di Fermat all'anello dei polinomi a coefficienti in Zp.

Nous étudions dans cette thèse quelques tests probabilistes de primalité, en particulier ceux qui, vraisemblablement à cause de leur simplicité et de leur rapidité d'éxécution, sont implantés dans les systèmes de calcul formel usuels. Nous commençons par présenter dans le chapitre 1 le test probabiliste de primalité le plus connu : le test de Rabin. Nous rappelons entre autres le théorème de Rabin, qui permet de majorer la probabilité d'échec de ce test. Nous donnons dans les chapitres 3 et 6 deux méthodes permettant de construire des nombres composés déclarés premiers par le test de Rabin des systèmes de calcul formel comme Axiom et Maple. Quelques rappels sur les lois de réciprocité, utiles pour la première de ces méthodes sont rassemblés dans le chapitre 2. Nous étudions aussi le test de Lucas (chapitre 4), d'un point de vue aussi algébrique que possible, en mettant en valeur l'analogie avec les pseudo-premiers classiques. Nous démontrons un analogue, pour les pseudo-premiers de Lucas, du théorème de Rabin. Précisément, nous montrons que, mises à part quelques rares exceptions bien cernées, le nombre de couples(P,Q) pour lesquels un nombre composé N est pseudo-premier de Lucas est majoré par 4N/15. Nous montrons aussi dans le chapitre 6 que l'une des méthodes proposées pour construire des pseudo-premiers forts classiques s'adapte pour produire des pseudo-premiers forts de Lucas. Nous étudions dans le chapitre 5, une fonction introduite dans le chapitre précédent et qui décrit le nombre d'éléments de norme 1 dans l'anneau des entiers d'un corps quadratique par un entier rationnel. Enfin, nous terminons par un aperçu de quelques autres tests probabilistes de primalité, et utilisons dans quelques cas particuliers, des variantes de la méthodedu chapitre 6 pour produire des nombres admissibles pour un test dû à Adams, Kurtz, Schanks et Williams, et pour produire des pseudo-premiers elliptiques forts.

Nous decrivons dans cette these l'application de la theorie des courbes elliptiques definies sur les corps finis a la construction d'algorithmes efficaces de primalite exacte. Nous faisons le lien entre le probleme de la representation des nombres premiers par des formes quadratiques binaires et la theorie du corps de classe. A ce propos, nous donnons un algorithme rapide de construction du corps de classe d'un corps quadratique imaginaire a l'aide des fonctions de weber. Nous en deduisons le calcul des invariants des courbes elliptiques a multiplication complexe dans un corps fini en resolvant par radicaux l'equation de definition du corps de classe, dans le corps des complexes d'abord, modulo un nombre premier ensuite. Nous montrons comment generaliser les algorithmes de preuve de primalite les plus classiques (reciproques du theoreme de fermat) en utilisant les courbes elliptiques. A l'encontre de son concurrent le plus serieux (sommes de jacobi), l'algorithme qui en resulte produit un certificat de primalite. D'un point de vue pratique, nous detaillons toutes les phases de l'implantation de l'algorithme, d'abord sur une station de travail, puis sur plusieurs stations d'une maniere distribuee. A chaque etape, nous presentons les meilleurs algorithmes connus pour resoudre chaque probleme particulier (calculs sur les courbes elliptiques, recherche de racines de polynomes modulo un nombre premier,. . . ). Nous decrivons egalement l'utilisation d'un multiplicateur hardware pour le calcul du produit de grands entiers, qui permet d'accelerer considerablement les calculs. Enfin, nous utilisons le programme pour la recherche de nombres premiers de cent chiffres (utiles en cryptographie) et pour la certification de nombres de trois cents a trois mille chiffres

This paper follows up the factorization of integers. Factorization is the most popular and used method for RSA cryptoanalysis. The SIQS was chosen as a factorization method that will be used in this paper. Although SIQS is the fastest method (up to 100 digits), it can't be effectively computed at polynomial time, so it's needed to look up for options, how to speed up the method as much as possible. One of the possible ways is paralelization. In this case OpenMP was used. Other possible way is optimalization. The goal of this paper is also to show, how easily is possible to use paralelizion and thanks to detailed analyzation the source codes one can reach relatively large speed up. Used method of iterative optimalization showed itself as a very effective tool. Using this method the implementation of SIQS achieved almost 100 multiplied speed up and at some parts of the code even more.

L'information est très précieuse, c'est pourquoi au moment de la stocker ou de la transmettre, il est nécessaire de la protéger. La factorisation des grands entiers est un problème diffcile, elle constitue ainsi une base de sécurité en cryptographie asymétrique. Il est donc très utile de pouvoir déterminer la primalité de grands entiers afin de construire des entiers difficilement factorisables qui pourront servir en cryptographie asymétrique. Pour ce faire on a recours aux tests de primalité. Le test AKS (inventé par Agrawal, Kayal et Saxena) est un algorithme polynômial déterministe de preuve de primalité qui a été publié en Août 2002 ("Primes is in P"). L'algorithme ECPP (Elliptic Curves Primality Proving) est un test de primalité probabiliste. Il a été proposé par A. O. L Atkin en 1988 et c'est l'un des tests de primalité les plus puissants utilisés en pratique. L'objet de cette thèse est de donner un critère de primalité de type AKS qui repose sur un anneau des périodes elliptiques. Un tel anneau est obtenu comme anneau résiduel le long d'une section de torsion d'une courbe elliptique définie sur Z/nZ. Cette section joue le rôle dévolu à la racine de l'unité dans le test AKS d'origine. Après avoir énoncé un critère général de primalité en termes d'extension étale de Z/nZ munie d'un automorphisme, nous montrons comment construire de telles extensions à partir d'isogénies entre courbes elliptiques modulo n
Information is very precious, this is the reason why it must be protected both in databasis and during transmission. Integer factoring is a diffcult problem and a cornerstone for safety in asymmetric cryptography. Thus it is very important to be able to check for the primality of big integers for asymetric cryptography. To do this we use primality tests. The AKS test is a deterministic polynomial time primality proving algorithm proposed by Agrawal, Kayal and Saxena in August 2002 ('Primes is in P'). The Elliptic Curves Primality Proving (ECPP), proposed by A. O. L. Atkin in 1988, is a probabilistic test. It is one of the most powerful primality tests that is used in practice. The purpose of this thesis is to give an elliptic version of the AKS primality criterion involving a ring of elliptic periods. Such a ring is obtained as a residue ring at a torsion section on an elliptic curve defined on Z/nZ. This section plays the role of the root of unity in the original AKS test. We give a general criterion in terms of etale extensions of Z/nZ equipped with an automorphism, and we show how to build such extensions using isogenies between elliptic curves modulo n

Con questa tesi verrà spiegata l'intrinseca connessione tra la matematica della teoria dei numeri e l'affidabilità e sicurezza dei crittosistemi asimmetrici moderni. I principali argomenti trattati saranno la crittografia a chiave pubblica ed il problema della verifica della primalità. Nei primi capitoli si capirà cosa vuol dire crittografia e qual è la differenza tra asimmetria e simmetria delle chiavi. Successivamente verrà fatta maggiore luce sugli utilizzi della crittografia asimmetrica, mostrando tecniche per: comunicare in modo confidenziale, scambiare in modo sicuro chiavi private su un canale insicuro, firmare messaggi, certificare identità e chiavi pubbliche. La tesi proseguirà con la spiegazione di quale sia la natura dei problemi alla base della sicurezza dei crittosistemi asimmetrici oggigiorno più diffusi, illustrando brevemente le novità introdotte dall'avvento dei calcolatori quantistici e dimostrando l'importanza che riveste in questo contesto il problema della verifica della primalità. Per concludere verrà fatta una panoramica di quali sono i test di primalità più efficienti ed efficaci allo stato dell'arte, presentando una nuova tecnica per migliorare l'affidabilità del test di Fermat mediante un nuovo algoritmo deterministico per fattorizzare gli pseudoprimi di Carmichael, euristicamente in tempo O~( log^3{n}), poi modificato sfruttando alcune proprietà del test di Miller per ottenere un nuovo test di primalità deterministico ed euristico con complessità O~( log^2{n} ) e la cui probabilità di errore tende a 0 con n che tende ad infinito.

碩士
國立成功大學
數學系應用數學碩博士班
96
In August 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena presented a remarkable algorithm (the AKS algorithm). It is an unconditional deterministic polynomial-time primality testing algorithm that determines whether an input number is prime or composite. In this thesis, the basic idea, the algorithm, the proof of correctness and the time complexity analysis of AKS algorithm, described in detail.

In 1980, L. Adleman, C. Pomerance, and R. Rumely invented the first cyclotomicprimality test, and shortly after, in 1981, a simplified and more efficient versionwas presented by H.W. Lenstra for the Bourbaki Seminar. Later, in 2008, ReneSchoof presented an updated version of Lenstra's primality test. This thesis presents adetailed description of the cyclotomic primality test as described by Schoof, along withsuggestions for implementation. The cornerstone of the test is a prime congruencerelation similar to Fermat's little theorem" that involves Gauss or Jacobi sumscalculated over cyclotomic fields. The algorithm runs in very nearly polynomial time.This primality test is currently one of the most computationally efficient tests and isused by default for primality proving by the open source mathematics systems Sageand PARI/GP. It can quickly test numbers with thousands of decimal digits.

碩士
輔仁大學
數學系碩士班
106
Abstract In this master thesis, we will briefly introduce some well-known results on Mersenne and Fermat numbers in Chapter 1. In Section 1.3, we will also introduce the Lucas-Lehmer sequences and outline their useful corresponding properties with complete proofs. In Chapter 2, we will study the Lucas-Lehmer primality test for Mersenne numbers. And in Chapter 3, we will study the Pepin{'}s primality test for Fermat numbers. Via Lucas-Lehmer sequences, both tests share a common nature. We will outline these ideas with complete discussions here.