Prime Numbers | springerprofessional.de

Springer Professional

nach oben

2001 | Buch

Kapitel lesen Erstes Kapitel lesen

Prime Numbers

A Computational Perspective

verfasst von: Richard Crandall, Carl Pomerance

Verlag: Springer New York

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

In this volume we have endeavored to provide a middle ground-hopefully even a bridge-between "theory" and "experiment" in the matter of prime numbers. Of course, we speak of number theory and computer experiment. There are great books on the abstract properties of prime numbers. Each of us working in the field enjoys his or her favorite classics. But the experimental side is relatively new. Even though it can be forcefully put that computer science is by no means young, as there have arguably been four or five computer "revolutions" by now, it is the case that the theoretical underpinnings of prime numbers go back centuries, even millennia. So, we believe that there is room for treatises based on the celebrated classical ideas, yet authored from a modern computational perspective. Design and scope of this book The book combines the essentially complementary areas of expertise of the two authors. (One author (RC) is more the computationalist, the other (CP) more the theorist. ) The opening chapters are in a theoretical vein, even though some explicit algorithms are laid out therein, while heavier algorithmic concentration is evident as the reader moves well into the book. Whether in theoretical or computational writing mode, we have tried to provide the most up-to-date aspects of prime-number study. What we do not do is sound the very bottom of every aspect.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Primes!

Abstract

Prime numbers belong to an exclusive world of intellectual conceptions. We speak of those marvelous notions that enjoy simple, elegant description, yet lead to extreme—one might say unthinkable—complexity in the details. The basic notion of primality can be accessible to a child, yet no human mind harbors anything like a complete picture. In modern times, while theoreticians continue to grapple with the profundity of the prime numbers, vast toil and resources have been directed toward the computational aspect, the task of finding, characterizing, and applying the primes in other domains. It is this computational aspect on which we concentrate in the ensuing chapters. But we shall often digress into the theoretical domain in order to illuminate, justify, and underscore the practical import of the computational algorithms.

Richard Crandall, Carl Pomerance

Chapter 2. Number-Theoretical Tools

Abstract

In this chapter we focus specifically on those fundamental tools and associated computational algorithms that apply to prime number and factorization studies. Enhanced integer algorithms, including various modern refinements of the classical ones of the present chapter, are detailed in Chapter 9. The reader may wish to refer to that chapter from time to time, especially when issues of computational complexity and optimization are paramount.

Richard Crandall, Carl Pomerance

Chapter 3. Recognizing Primes and Composites

Abstract

Given a large number, how might one quickly tell whether it is prime or composite? In this chapter we begin to answer this fundamental question.

Richard Crandall, Carl Pomerance

Chapter 4. Primality Proving

Abstract

In Chapter 3 we discussed probabilistic methods for quickly recognizing composite numbers. If a number is not declared composite by such a test, it is either prime, or we have been unlucky in our attempt to prove the number composite. Since we do not expect to witness inordinate strings of bad luck, after a while we become convinced that the number is prime. We do not, however, have a proof; rather, we have a conjecture substantiated by numerical experiments. This chapter is devoted to the topic of how one might actually prove that a number is prime.

Richard Crandall, Carl Pomerance

Chapter 5. Exponential Factoring Algorithms

Abstract

For almost all of the multicentury history of factoring, the only algorithms available were exponential, namely, the running time was, in the worst case, a fixed positive power of the number being factored. But in the early 1970s, subexponential factoring algorithms began to come “on line.” These methods, discussed in the next chapter, have their running time to factor n bounded by an expression of the form n°⁽¹⁾ One might wonder, then, why the current chapter exists in this book. We have several reasons for including it.

Richard Crandall, Carl Pomerance

Chapter 6. Subexponential Factoring Algorithms

Abstract

The methods of this chapter include two of the three basic workhorses of modern factoring, the quadratic sieve (QS) and the number field sieve (NFS). (The third workhorse, the elliptic curve method (ECM), is described in Chapter 7.) The quadratic sieve and number field sieve are direct descendants of the continued fraction factoring method of Brillhart and Morrison, which was the first subexponential factoring algorithm on the scene. The continued fraction factoring method, which was introduced in the early 1970s, allowed complete factorizations of numbers of around 50 digits, when previously, about 20 digits had been the limit. The quadratic sieve and the number field sieve, each with its strengths and domain of excellence, have pushed our capability for complete factorization from 50 digits to now over 150 digits for the size of numbers to be routinely factored. By contrast, the elliptic curve method has allowed the discovery of prime factors up to 50 digits and beyond, with fortunately weak dependence on the size of number to be factored. We include in this chapter a small discussion of rigorous factorization methods that in their own way also represent the state of the art. We also discuss briefly some subexponential discrete logarithm algorithms for the multiplicative groups of finite fields.

Richard Crandall, Carl Pomerance

Chapter 7. Elliptic Curve Arithmetic

Abstract

The history of what are called elliptic curves goes back well more than a century. Originally developed for classical analysis, elliptic curves have found their way into abstract and computational number theory, and now sit squarely as a primary tool. Like the prime numbers themselves, elliptic curves have the wonderful aspects of elegance, complexity, and power. Elliptic curves are not only celebrated algebraic constructs; they also provide considerable leverage in regard to prime number and factorization studies. Elliptic curve applications even go beyond these domains; for example, they have an increasingly popular role in modern cryptography, as we discuss in Section 8.1.3.

Richard Crandall, Carl Pomerance

Chapter 8. The Ubiquity of Prime Numbers

Abstract

It is often remarked that prime numbers finally found a legitimate practical application in the domain of cryptography. The cryptographic relevance is not disputed, but there are many other applications of the majestic primes. Some applications are industrial—such as applications in numerical analysis, applied mathematics, and other applied sciences—while some are of the “conceptual feedback” variety, in which primes and their surrounding concepts are used in theoretical work outside of, say, pure number theory. In this lucrative research mode, primes are used within algorithms that might appear a priori independent of primes, and so on. It seems fair to regard the prime number concept as ubiquitous, since the primes appear in so very many disparate domains of thought.

Richard Crandall, Carl Pomerance

Chapter 9. Fast Algorithms for Large-Integer Arithmetic

Abstract

In this chapter we explore the galaxy of “fast” algorithms that admit of applications in prime number and factorization computations. In modern times, it is of paramount importance to be able to manipulate multiple-precision integers, meaning integers that in practice, on prevailing machinery, have to be broken up into pieces, with machine operations to involve those pieces, with a view to eventual reassembly of desired results. Although multiple-precision addition and subtraction of, integers is quite common in numerical studies, we assume that notions of these very simple fundamental operations are understood, and start with multiplication, which is perhaps the simplest arithmetic algorithm whose classical form admits of genuine enhancements.

Richard Crandall, Carl Pomerance

Backmatter

Titel: Prime Numbers
verfasst von: Richard Crandall
Carl Pomerance
Copyright-Jahr: 2001
Verlag: Springer New York
Electronic ISBN: 978-1-4684-9316-0
Print ISBN: 978-1-4684-9318-4
DOI: https://doi.org/10.1007/978-1-4684-9316-0