Section 8.1. Prime Numbers


[Page 236]

8.1. Prime Numbers[1]

[1] In this section, unless otherwise noted, we deal only with the nonnegative integers. The use of negative integers would introduce no essential differences.

A central concern of number theory is the study of prime numbers. Indeed, whole books have been written on the subject (e.g., [CRAN01], [RIBE96]). In this section we provide an overview relevant to the concerns of this book.

An integer p > 1 is a prime number if and only if its only divisors[2] are ± 1 and ±p. Prime numbers play a critical role in number theory and in the techniques discussed in this chapter. Table 8.1 shows the primes less than 2000. Note the way the primes are distributed. In particular, note the number of primes in each range of 100 numbers.

[2] Recall from Chapter 4 that integer a is said to be a divisor of integer b if there is no remainder on division. Equivalently, we say that a divides b.

Table 8.1. Primes under 2000
(This item is displayed on page 237 in the print version)


Any integer a > 1 can be factored in a unique way as

Equation 8-1


where p1 < p2 < ... < pt are prime numbers and where each is a positive integer. This is known as the fundamental theorem of arithmetic; a proof can be found in any text on number theory.

91

= 7 x 13

3600

= 24 x 32 x 52

11011

= 7 x 112 x 13


It is useful for what follows to express this another way. If P is the set of all prime numbers, then any positive integer a can be written uniquely in the following form:


The right-hand side is the product over all possible prime numbers p; for any particular value of a, most of the exponents ap will be 0.

The value of any given positive integer can be specified by simply listing all the nonzero exponents in the foregoing formulation.

The integer 12 is represented by {a2 = 2, a3 = 1}.

The integer 18 is represented by {a2 = 1, a3 = 2}.

The integer 91 is represented by {a7 = 2, a13 = 1}.


Multiplication of two numbers is equivalent to adding the corresponding exponents. Given a . Define k = ab We know that the integer k can be expressed as the product of powers of primes: . It follows that kp = ap + bp for all p


[Page 238]

k = 12 x 18 = (22 x 3) x (2 x 32) = 216

k2 = 2 + 1 = 3; k3 = 1 + 2 = 3

216 = 23 x 33 = 8 x 27


What does it mean, in terms of the prime factors of a and b, to say that a divides b? Any integer of the form can be divided only by an integer that is of a lesser or equal power of the same prime number, pj with j Given , If a|b, then ap p.

a

= 12;b = 36; 12|36

12

= 22 x 3; 36 = 22 x 32

a2

= 2 = b2

a3

= 1 2 =

Thus, the inequality ap It is easy to determine the greatest common divisor[3] of two positive integers if we express each integer as the product of primes.

[3] Recall from Chapter 4 that the greatest common divisor of integers a and b, expressed gcd(a, b), is an integer c that divides both a and b without remainder and that any divisor of a and b is a divisor of c.

300

= 22 x 31 x 52

18

= 21 x 32

gcd(18,300)

= 21 x 31 x 50 = 6


The following relationship always holds:

If k = gcd(a,b) then kp = min(ap, bp) for all p

Determining the prime factors of a large number is no easy task, so the preceding relationship does not directly lead to a practical method of calculating the greatest common divisor.




Cryptography and Network Security Principles and Practices
Cryptography and Network Security (4th Edition)
ISBN: 0131873164
EAN: 2147483647
Year: 2005
Pages: 209

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