Chapter 1: Introduction

Team-Fly

Overview

God created the integers. All the rest is the work of man.

Leopold Kronecker

If you look at zero you see nothing; but look through it and you will see the world.

Robert Kaplan, The Nothing That Is: A Natural History of Zero

TO BE INVOLVED WITH MODERN cryptography is to dive willy-nilly into number theory, that is, the study of the natural numbers, one of the most beautiful areas of mathematics. However, we have no intention of becoming deep-sea divers who raise sunken treasure from the mathematical ocean floor, which in any case is unnecessary for cryptographic applications. Our goals are much more modest. On the other hand, there is no limit to the depth of involvement of number theory with cryptography, and many significant mathematicians have made important contributions to this area.

The roots of number theory reach back to antiquity. The Pythagoreansthe Greek mathematician and philosopher Pythagoras and his schoolwere already deeply involved in the sixth century B.C.E. with relations among the integers, and they achieved significant mathematical results, for example the famed Pythagorean theorem, which is a part of every school child's education. With religious zeal they took the position that all numbers should be commensurate with the natural numbers, and they found themselves on the horns of a serious dilemma when they discovered the existence of "irrational" numbers such as , which cannot be expressed as the quotient of two integers. This discovery threw the world view of the Pythagoreans into disarray, to the extent that they sought to suppress knowledge of the irrational numbers, a futile form of behavior oft repeated throughout human history.

Two of the oldest number-theoretic algorithms, which have been passed down to us from the Greek mathematicians Euclid (third century B.C.E.) and Eratosthenes (276195 B.C.E.), are closely related to the most contemporary encryption algorithms that we use every day to secure communication across the Internet. The "Euclidean algorithm" and the "sieve of Eratosthenes" are both quite up-to-date for our work, and we shall discuss their theory and application in Sections 10.1 and 10.5 of this book.

Among the most important founders of modern number theory are to be counted Pierre de Fermat (16011665), Leonhard Euler (17071783), Adrien Marie Legendre (17521833), Carl Friedrich Gauss (17771855), and Ernst Eduard Kummer (18101893). Their work forms the basis for the modern development of this area of mathematics and in particular the interesting application areas such as cryptography, with its asymmetric procedures for encryption and the generation of digital signatures (cf. Chapter 16). We could mention many more names of important contributors to this field, who continue to this day to be involved in often dramatic developments in number theory, and to those interested in a thrilling account of the history of number theory and its protagonists, I heartily recommend the book Fermats Last Theorem, by Simon Singh.

Considering that already as children we learned counting as something to be taken for granted and that we were readily convinced of such facts as that two plus two equals four, we must turn to surprisingly abstract thought constructs to derive the theoretical justification for such assertions. For example, set theory allows us to derive the existence and arithmetic of the natural numbers from (almost) nothing. This "almost nothing" is the empty (or null) set ø := { }, that is, the set that has no elements. If we consider the empty set to correspond to the number 0, then we are able to construct additional sets as follows. The successor 0+ of 0 is associated with the set 0+ := { 0 } = { ø }, which contains a single element, namely the null set. We give the successor of 0 the name 1, and for this set as well we can determine a successor, namely 1+ := { ø, { ø }}. The successor of 1, which contains 0 and 1 as its elements, is given the name 2. The sets thus constructed, which we have rashly given the names 0, 1, and 2, we identifynot surprisinglywith the well-known natural numbers 0, 1, and 2.

This principle of construction, which to every number x associates a successor x+ := x È { x } by adjoining x to the previous set, can be continued to produce additional numbers. Each number thus constructed, with the exception of 0, is itself a set whose elements constitute its predecessors. Only 0 has no predecessor. To ensure that this process continues ad infinitum, set theory formulates a special rule, called the axiom of infinity: There exists a set that contains 0 as well as the successor of every element that it contains.

From this postulated existence of (at least) one so-called successor set, which, beginning with 0, contains all successors, set theory derives the existence of a minimal successor set , which is itself a subset of every successor set. This minimal and thus uniquely determined successor set is called the set of natural numbers, in which we expressly include zero as an element.[1]

The natural numbers can be characterized by means of the axioms of Giuseppe Peano (18581932), which coincide with our intuitive understanding of the natural numbers:

  1. The successors of two unequal natural numbers are unequal: From n m, it follows that n+ m+, for all n, m Î .

  2. Every natural number, with the exception of 0, has a predecessor: = \ {0}.

  3. The principle of complete induction: If S , 0 Î S, and n Î S always imply n+ Î S, then S = .

The principle of complete induction makes it possible to derive the arithmetic operations with natural numbers in which we are interested. The fundamental operations of addition and multiplication can be defined recursively as follows. We begin with addition:

For every natural number n Î there exists a function sn from to such that

  1. sn (0) = n,

  2. sn (x+) = (sn(x))+ for all natural numbers x Î .

The value of the function sn(x) is called the sum n + x of n and x.

The existence of such functions sn for all natural numbers n Î must, however, be proved, since the infinitude of natural numbers does not a priori justify such an assumption. The existence proof goes back to the principle of complete induction, corresponding to Peano's third axiom above (see [Halm], Chapters 1113). For multiplication one proceeds analogously:

For every natural number n Î there exists a function pn from to such that

  1. pn(0) = 0,

  2. pn (x+) = pn(x) + n for all natural numbers x Î .

The value of the function pn(x) is called the product n · x of n and x.

As expected, multiplication is defined in terms of addition. For the arithmetic operations thus defined one can prove, through repeated application of complete induction on x in accordance with Axiom III, such well-known arithmetic laws as associativity, commutativity, and distributivity (cf. [Halm], Chapter 13). Although we usually use these laws without further ado, we shall help ourselves to them as much as we please in testing our FLINT functions (see Chapters 12 and 17).

In a similar way we obtain a definition of exponentiation, which we give here in view of the importance of this operation in what follows.

For every natural number n Î there exists a function en from to such that

  1. en(0) = 1,

  2. en (x+) = en(x) · n for every natural number x Î .

The value of the function en(x) is called the xth power nx of n.

With complete induction we can prove the power law

click to expand

to which we shall return in Chapter 6.

In addition to the calculational operations, the set of natural numbers has defined on it an order relation "<" that makes it possible to compare two elements n, m Î . Although this fact is worthy of our great attention from a set-theoretic point of view, here we shall content ourselves with noting that the order relation has precisely those properties that we know about and use in our everyday lives.

Now that we have begun with establishing the empty set as the sole fundamental building block of the natural numbers, we now proceed to consider the materials with which we shall be concerned in what follows. Although number theory generally considers the natural numbers and the integers as given and goes on to consider their properties without excessive beating about the bush, it is nonetheless of interest to us to have at least once taken a glance at a process of "mathematical cell division," a process that produces not only the natural numbers, but also the arithmetic operations and rules with which we shall be deeply involved from here on.

[1]It was not decisive for this choice that according to standard DIN 5473 zero belongs to the natural numbers. From the point of view of computer science, however, it is practical to begin counting at zero instead of 1, which is indicative of the important role played by zero as the neutral element for addition (additive identity).


Team-Fly


Cryptography in C and C++
Cryptography in C and C++
ISBN: 189311595X
EAN: 2147483647
Year: 2001
Pages: 127

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net