Encryption and Decryption using Vigenere with Cipher Block Chaining: Up to 50 dollars will be given

B-NumberTheory.pdf

Home >Computer Science homework help >Encryption and Decryption using Vigenere with Cipher Block Chaining: Up to 50 dollars will be given

APPENDIX B SOME ASPECTS OF NUMBER

THEORY

William Stallings

B.1 PRIME AND RELATIVELY PRIME NUMBERS ............................................ 2

Divisors ............................................................................................................ 2 Prime Numbers ............................................................................................... 3 Relatively Prime Numbers ............................................................................. 4

B.2 MODULAR ARITHMETIC ................................................................................ 5 Modular Arithmetic Operations ..................................................................... 7 Inverses ........................................................................................................... 8

B.3 FERMAT'S AND EULER'S THEOREMS ......................................................... 9 Fermat's Theorem ........................................................................................... 9 Euler's Totient Function ............................................................................... 10 Euler's Theorem ............................................................................................ 12

B-2

This appendix provides some background on number theory concepts

referenced in this book.

B.1 PRIME AND RELATIVELY PRIME NUMBERS

In this section, unless otherwise noted, we deal only with nonnegative

integers. The use of negative integers would introduce no essential

differences.

Divisors

We say that b ≠ 0 divides a if a = mb for some m, where a, b, and m are

integers. That is, b divides a if there is no remainder on division. The

notation b|a is commonly used to mean b divides a. Also, if b|a, we say that

b is a divisor of a. For example, the positive divisors of 24 are 1, 2, 3, 4, 6,

8, 12, and 24.

The following relations hold:

• If a|1, then a = ±1.

• If a|b and b|a, then a = ±b.

• Any b ≠ 0 divides 0.

• If b|g and b|h, then b|(mg + nh) for arbitrary integers m and n.

To see this last point, note that

If b|g, then g is of the form g = b × g1 for some integer g1.

If b|h, then h is of the form h = b × h1 for some integer h1.

B-3

mg + nh = mbg1 + nbh1 = b × (mg1 + nh1)

and therefore b divides mg + nh.

Prime Numbers

An integer p > 1 is a prime number if its only divisors are ±1 and ±p. Prime

numbers play a critical role in number theory and in the algorithms

discussed in Chapter 23.

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

�

a = p1 a1 p2

a2 … pt at

where p1 < p2 < . . . < pt are prime numbers and where each ai is a positive

integer. For example, 91 = 7 × 13; and 11011 = 7 × 112 × 13.

It is useful to cast this another way. If P is the set of all prime numbers,

then any positive integer can be written uniquely in the following form:

�

a = pap p∈P ∏ where each ap ≥ 0

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. Thus, the integer 12

is represented by {a2 = 2, a3 = 1}, and the integer 18 is represented by {a2

= 1, a3 = 2}. Multiplication of two numbers is equivalent to adding the

corresponding exponents:

B-4

k = mn → kp = mp + np for all p

What does it mean, in terms of these prime factors, to say that a|b?

Any integer of the form pk can be divided only by an integer that is of a

lesser or equal power of the same prime number, pj with j ≤ k. Thus, we can

say

a|b → ap ≤ bp for all p

Relatively Prime Numbers

We will use the notation gcd(a, b) to mean the greatest common divisor

of a and b. The positive integer c is said to be the greatest common divisor

of a and b if

1. c is a divisor of a and of b;

2. any divisor of a and b is a divisor of c.

An equivalent definition is the following:

gcd(a, b) = max[k, such that k|a and k|b]

Because we require that the greatest common divisor be positive, gcd(a,

b) = gcd(a, –b) = gcd(–a, b) = gcd(–a, –b). In general, gcd(a, b) = gcd( | a

|, | b | ). For example, gcd(60, 24) = gcd(60, –24) = 12. Also, because all

nonzero integers divide 0, we have gcd(a, 0) = | a |.

B-5

It is easy to determine the greatest common divisor of two positive

integers if we express each integer as the product of primes. For example,

300 = 22 × 31 × 52; 18 = 21 × 32; gcd(18, 300) = 21 × 31 × 50 = 6.

In general,

k = gcd(a, b) → 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 way of calculating the

greatest common divisor.

The integers a and b are relatively prime if they have no prime factors

in common; that is, if their only common factor is 1. This is equivalent to

saying that a and b are relatively prime if gcd(a, b) = 1. For example, 8 and

15 are relatively prime because the divisors of 8 are 1, 2, 4, and 8, and the

divisors of 15 are 1, 3, 5, and 15, so 1 is the only number on both lists.

B.2 MODULAR ARITHMETIC

Given any positive integer n and any nonnegative integer a, if we divide a by

n, we get an integer quotient q and an integer remainder r that obey the

following relationship:

a = qn + r 0 ≤ r < n; q = ⎣a/n⎦

where ⎣x⎦ is the largest integer less than or equal to x.

Figure B.1 demonstrates that, given a and positive n, it is always

possible to find q and r that satisfy the preceding relationship. Represent the

integers on the number line; a will fall somewhere on that line (positive a is

shown, a similar demonstration can be made for negative a). Starting at 0,

B-6

n 2n 3n qn (q + 1)na

Figure B.1 The Relationship a = qn + r; 0 ! r < n

(a) General relationship

0 15

30 = 2 15

(b) Example: 70 = (4 15) + 10

45 = 3 15

60 = 4 15

75 = 5 15

proceed to n, 2n, up to qn such that qn ≤ a and (q + 1)n > a. The distance

from qn to a is r, and we have found the unique values of q and r. The

remainder r is often referred to as a residue.

If a is an integer and n is a positive integer, we define a mod n to be the

remainder when a is divided by n. Thus, for any integer a, we can always

write

a = ⎣a/n⎦ × n + (a mod n)

Two integers a and b are said to be congruent modulo n, if (a mod n)

= (b mod n). This is written a ≡ b mod n. For example, 73 ≡ 4 mod 23; and

21 ≡ –9 mod 10. Note that if a ≡ 0 mod n, then n|a.

The modulo operator has the following properties:

1. a ≡ b mod n if n|(a – b)

2. (a mod n) = (b mod n) implies a ≡ b mod n

B-7

3. a ≡ b mod n implies b ≡ a mod n

4. a ≡ b mod n and b ≡ c mod n imply a ≡ c mod n

To demonstrate the first point, if n|(a – b), then (a – b) = kn for some

k. So we can write a = b + kn. Therefore, (a mod n) = (remainder when b +

kn is divided by n) = (remainder when b is divided by n) = (b mod n). The

remaining points are as easily proved.

Modular Arithmetic Operations

The (mod n) operator maps all integers into the set of integers {0, 1, . . . (n

– 1)}. This suggests the question, Can we perform arithmetic operations

within the confines of this set? It turns out that we can; the technique is

known as modular arithmetic.

Modular arithmetic exhibits the following properties:

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n

2. [(a mod n) – (b mod n)] mod n = (a – b) mod n

3. [(a mod n) × (b mod n)] mod n = (a × b) mod n

We demonstrate the first property. Define (a mod n) = ra and (b mod n)

= rb. Then we can write a = ra + jn for some integer j and b = rb + kn for

some integer k. Then

(a + b) mod n = (ra + jn + rb + kn) mod n

= (ra + rb + (k + j)n) mod n

= (ra + rb) mod n

= [(a mod n) + (b mod n)] mod n

B-8

The remaining properties are as easily proved.

Inverses

As in ordinary arithmetic, we can write the following:

if (a + b) ≡ (a + c) (mod n) then b ≡ c (mod n) (B.1)

(5 + 23) ≡ (5 + 7) (mod 8); 23 ≡ 7 (mod 8)

For example, (5 + 23) ≡ (5 + 7) (mod 8) implies that 23 ≡ 7 (mod 8).

Equation (B.1) is consistent with the existence of an additive inverse.

Adding the additive inverse of a to both sides of Equation (B.1), we have

((–a) + a + b) ≡ ((–a) + a + c) (mod n)

b ≡ c (mod n)

However, the following statement is true only with the attached

condition:

if (a × b) ≡ (a × c) (mod n)

then b ≡ c (mod n) if a is relatively prime to n (B.2)

Similar to the case of Equation (B,1), we can say that Equation (B.2) is

consistent with the existence of a multiplicative inverse. Applying the

multiplicative inverse of a to both sides of Equation (B.2), we have

((a–1)ab) ≡ ((a–1)ac) (mod n)

b ≡ c (mod n)

B-9

The proof that we must add the condition in Equation (B.2) is beyond the

scope of this book but is explored in [STAL11b].

B.3 FERMAT'S AND EULER'S THEOREMS

Two theorems that play important roles in public-key cryptography are

Fermat's theorem and Euler's theorem.

Fermat's Theorem1

Fermat's theorem states the following: If p is prime and a is a positive

integer not divisible by p, then

ap–1 ≡ 1 (mod p) (B.3)

Proof: Consider the set of positive integers less than p: {1, 2, …, p – 1} and

multiply each element by a, modulo p, to get the set X = {a mod p, 2a mod

p, . . . (p – 1)a mod p}. None of the elements of X is equal to zero because

p does not divide a. Furthermore, no two of the integers in X are equal. To

see this, assume that ja ≡ ka (mod p), where 1 ≤ j < k ≤ p – 1. Because a is

relatively prime to p, we can eliminate a from both sides of the equation

[see Equation (B.2)] resulting in j ≡ k (mod p). This last equality is

impossible because j and k are both positive integers less than p. Therefore,

we know that the (p – 1) elements of X are all positive integers, with no two

elements equal. We can conclude the X consists of the set of integers {1, 2,

…, p – 1} in some order. Multiplying the numbers in both sets and taking the

result mod p yields

1 This is sometimes referred to as Fermat's little theorem.

B-10

a × 2a × . . . × (p – 1)a ≡ [(1× 2 × …× (p – 1)] (mod p)

ap–1(p – 1)! ≡ (p – 1)! (mod p)

We can cancel the (p – 1)! term because it is relatively prime to p [see

Equation (B.2)]. This yields Equation (B.3).

a = 7, p = 19 72 = 49 ≡ 11 (mod 19) 74 ≡ 121 ≡ 7 (mod 19) 78 ≡ 49 ≡ 11 (mod 19) 716 ≡ 121 ≡ 7 (mod 19) ap–1 = 718 = 716 × 72 ≡ 7 × 11 ≡ 1 (mod 19)

An alternative form of Fermat's theorem is also useful: If p is prime and

a is a positive integer, then

ap ≡ a (mod p) (B.4)

Note that the first form of the theorem [Equation (B.3)] requires that a be

relatively prime to p, but this form does not.

p = 5, a = 3 ap = 35 = 243 ≡ 3 (mod 5) = a (mod p) p = 5, a = 10 ap = 105 = 100000 ≡ 10 (mod 5) ≡ 0 (mod 5) = a (mod p)

Euler's Totient Function

Before presenting Euler's theorem, we need to introduce an important

quantity in number theory, referred to as Euler's totient function and written

φ(n), defined as the number of positive integers less than n and relatively

prime to n.

B-11

Determine φ(37) and φ(35). Because 37 is prime, all of the positive integers from 1 through 36 are relatively prime to 37. Thus φ(37) = 36. To determine φ(35), we list all of the positive integers less than 35 that are relatively prime to it: 1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34. There are 24 numbers on the list, so φ(35) = 24.

Table B.1 lists the first 30 values of φ(n). The value φ(1) is without

meaning but is defined to have the value 1.

Table B.1 Some Values of Euler's Totient Function φ(n)

n φ(n) n φ(n) n φ(n)

1 1 11 10 21 12

2 1 12 4 22 10

3 2 13 12 23 22

4 2 14 6 24 8

5 4 15 8 25 20

6 2 16 8 26 12

7 6 17 16 27 18

8 4 18 6 28 12

9 6 19 18 29 28

10 4 20 8 30 8

It should be clear that for a prime number p,

B-12

φ(p) = p – 1

Now suppose that we have two prime numbers p and q, with p ≠ q. Then we

can show that for n = pq,

φ(n) = φ(pq) = φ(p) × φ(q) = (p – 1) × (q – 1)

To see that φ(n) = φ(p) × φ(q), consider that the set of positive integers less

that n is the set {1, . . . , (pq – 1)}. The integers in this set that are not

relatively prime to n are the set {p, 2p, . . . , (q – 1)p} and the set {q, 2q, .

. . , (p – 1)q}. Accordingly,

φ(n) = (pq – 1) – [(q – 1) + (p – 1)]

= pq – (p + q) +1

= (p – 1) × (q – 1)

= φ(p) × φ(q)

φ(21) = φ(3) × φ(7) = (3 – 1) × (7 – 1) = 2 × 6 = 12 where the 12 integers are {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}

Euler's Theorem

Euler's theorem states that for every a and n that are relatively prime,

aφ(n) ≡ 1 (mod n) (B.5)

a = 3; n = 10; φ(10) = 4 aφ(n) = 34 = 81 ≡ 1 (mod 10) = 1 (mod n) a = 2; n = 11; φ(11) = 10 aφ(n) = 210 = 1024 ≡ 1 (mod 11) = 1 (mod n)

B-13

Proof: Equation (B.5) is true if n is prime, because in that case φ(n) = (n –

1) and Fermat's theorem holds. However, it also holds for any integer n.

Recall that φ(n) is the number of positive integers less than n that are

relatively prime to n. Consider the set of such integers, labeled as follows:

R = {x1, x2, . . ., xφ(n)}

That is, each element xi of R is a unique positive integer less than n with

gcd(xi, n) = 1. Now multiply each element by a, modulo n:

S = {(ax1 mod n), (ax2 mod n), . . ., (axφ(n) mod n)}

The set S is a permutation of R, by the following line of reasoning:

1. Because a is relatively prime to n and xi is relatively prime to n, axi

must also be relatively prime to n. Thus, all the members of S are

integers that are less than n and that are relatively prime to n.

2. There are no duplicates in S. Refer to Equation (B.2). If axi mod n =

axj mod n, then xi = xj.

Therefore,

B-14

axi mod n( ) i= 1

φ n( ) ∏ = xi

i =1

φ n( ) ∏

axi i= 1

φ n( ) ∏ ≡ xi

i =1

φ n( ) ∏ mod n( )

aφ n( ) × xi i =1

φ n( ) ∏

⎡

⎣ ⎢ ⎢

⎤

⎦ ⎥ ⎥ ≡ xi

i =1

φ n( ) ∏ mod n( )

aφ n( ) ≡ 1 mod n( )

This is the same line of reasoning applied to the proof of Fermat's

theorem.

As is the case for Fermat's theorem, an alternative form of the theorem

is also useful:

aφ(n)+1 ≡ a (mod n) (B.6)

Again, similar to the case with Fermat's theorem, the first form of Euler's

theorem [Equation (B.6)] requires that a be relatively prime to n, but this

form does not.