Primality Testing for Beginners

Last updated

Primality Testing for Beginners is an undergraduate-level mathematics book on primality tests, methods for testing whether a given number is a prime number, centered on the AKS primality test, the first method to solve this problem in polynomial time. It was written by Lasse Rempe-Gillen and Rebecca Waldecker, and originally published in German as Primzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie (Vieweg+Teubner, 2009). [1] [2] It was translated into English as Primality Testing for Beginners and published in 2014 by the American Mathematical Society, as volume 70 of their Student Mathematical Library book series. [2] [3] [4] [5] A second German-language edition was publisher by Springer in 2016.

Contents

Topics

Primality Testing for Beginners has seven chapters, divided into two parts: four chapters on background material in number theory and computational complexity theory, and three on the AKS primality test. [1] [5]

Chapter 1 includes basic material on number theory, including the fundamental theorem of arithmetic on unique factorization into primes, the binomial theorem, the Euclidean algorithm for greatest common divisors, and the sieve of Eratosthenes for generating the sequence of prime numbers. Chapter 2 begins the study of algorithms and their complexity, including algorithms for basic computations in arithmetic, the notion of computability, polynomial-time algorithms, randomization, and nondeterministic polynomial time. In randomized algorithms, it introduces the distinction between Las Vegas algorithms that always return the correct answer after a random amount of time (such as quicksort) and Monte Carlo algorithms for which there is a small probability of getting a wrong answer (exemplified by algorithms based on the Schwartz–Zippel lemma for polynomial identity testing). Chapter 3 provides additional material in number theory, including the Chinese remainder theorem, Fermat's little theorem, and the Fermat primality test based on it. It also introduces calculation with polynomials and with modular arithmetic. The first part of the book concludes with chapter 4, on the history of prime numbers and primality testing, including the prime number theorem (in a weakened form), applications of prime numbers in cryptography, and the widely used Miller–Rabin primality test, which runs in randomized polynomial time. [5]

Chapter 5 generalizes Fermat's little theorem from numbers to polynomials, and introduces a randomized primality test based in this generalization. Chapter 6 provides the key mathematical results behind the correctness of the AKS primality test, and chapter 7 describes the test itself. [5] Both the correctness and the polynomial running time of the algorithm are proven rigorously. [3] Exercises are included in each chapter, and a section at the end of the book provides answers to some of them. [1] [2] Another appendix lists some unsolved problems from number theory. [3]

Audience and reception

Although primarily for undergraduate students of mathematics, Primality Testing for Beginners requires very little background knowledge, and may also be suitable for advanced secondary school students. [2] [3] It is based on a summer program for students at this level, run by the authors in Germany with the goal of introducing the students to recent research. [4]

Reviewers Robin Chapman and Jeffrey Ehme agree that the overall content of the book is probably too slight to use it as the main textbook for an undergraduate number theory course, but that it could be a good supplement for such a course, or for a course in cryptography. [3] [4] Reviewer Frederic Green recommends it as a good introduction to mathematical research more generally, and also suggests its use by researchers as a quick reference on primality testing. [5]

Related Research Articles

In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is called a composite number, or it is not, in which case it is called a prime number. For example, 15 is a composite number because 15 = 3 · 5, but 7 is a prime number because it cannot be decomposed in this way. If one of the factors is composite, it can in turn be written as a product of smaller factors, for example 60 = 3 · 20 = 3 · (5 · 4). Continuing this process until every factor is prime is called prime factorization; the result is always unique up to the order of the factors by the prime factorization theorem.

<span class="mw-page-title-main">Modular arithmetic</span> Computation modulo a fixed integer

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

<span class="mw-page-title-main">Number theory</span> Mathematics of integer properties

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers, or defined as generalizations of the integers.

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.

In number theory, Fermat's little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. The number 2p + 1 associated with a Sophie Germain prime is called a safe prime. For example, 11 is a Sophie Germain prime and 2 × 11 + 1 = 23 is its associated safe prime. Sophie Germain primes and safe primes have applications in public key cryptography and primality testing. It has been conjectured that there are infinitely many Sophie Germain primes, but this remains unproven.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and

The AKS primality test is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite and this without relying on mathematical conjectures such as the generalized Riemann hypothesis. The proof is also notable for not relying on the field of analysis. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

In number theory, a provable prime is an integer that has been calculated to be prime using a primality-proving algorithm. Boot-strapping techniques using Pocklington primality test are the most common ways to generate provable primes for cryptography. Contrast with probable prime, which is likely to be prime, based on the output of a probabilistic primality test.

In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself.

<i>From Here to Infinity</i> (book) 1996 book by Ian Stewart

From Here to Infinity: A Guide to Today's Mathematics, a 1996 book by mathematician and science popularizer Ian Stewart, is a guide to modern mathematics for the general reader. It aims to answer questions such as "What is mathematics?", "What is it for " and "What are mathematicians doing nowadays?". Author Simon Singh describes it as "An interesting and accessible account of current mathematical topics".

This is a timeline of pure and applied mathematics history. It is divided here into three stages, corresponding to stages in the development of mathematical notation: a "rhetorical" stage in which calculations are described purely by words, a "syncopated" stage in which quantities and common algebraic operations are beginning to be represented by symbolic abbreviations, and finally a "symbolic" stage, in which comprehensive notational systems for formulas are the norm.

A pseudoprime is a probable prime that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.

<span class="mw-page-title-main">Andrew Sutherland (mathematician)</span>

Andrew Victor Sutherland is an American mathematician and Principal Research Scientist at the Massachusetts Institute of Technology. His research focuses on computational aspects of number theory and arithmetic geometry. He is known for his contributions to several projects involving large scale computations, including the Polymath project on bounded gaps between primes, the L-functions and Modular Forms Database, the sums of three cubes project, and the computation and classification of Sato-Tate distributions.

<span class="mw-page-title-main">Rebecca Waldecker</span> German mathematician

Rebecca Anne Hedwig Waldecker is a German mathematician specializing in group theory. She is professor for algebra at Martin Luther University of Halle-Wittenberg.

References

  1. 1 2 3 Meidl, Wilfried, "Review of Primzahltests für Einsteiger", zbMATH , Zbl   1195.11003
  2. 1 2 3 4 Wagstaff, Samuel S. Jr., "Review of Primality Testing for Beginners", MathSciNet , MR   3154407
  3. 1 2 3 4 5 Chapman, Robin (July 2014), "Review of Primality Testing for Beginners" (PDF), London Mathematical Society Newsletter, no. 438, p. 49
  4. 1 2 3 Ehme, Jeffrey (November 2016), "A joy to review: Two books about primes and factoring", Cryptologia, 41 (1): 97–100, doi:10.1080/01611194.2016.1236625, S2CID   36760384
  5. 1 2 3 4 5 Green, Frederic (June 2016), "Review of Primality Testing for Beginners" (PDF), ACM SIGACT News, 47 (2): 6–9, doi:10.1145/2951860.2951863, S2CID   26146309
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.