|
[http://en.wikipedia.org/wiki/user:Unfinishedchaos en_Wikipedia:UnfinishedChaos]
[http://de.wikipedia.org/wiki/benutzer:Unfinishedchaos de_Wikipedia:UnfinishedChaos]
Introduction to Number Theory
2.1 Prime and Relatively Prime Numbers
A central concern of number theory are prime numbers In this section we provide an overview relevant to the concerns of this book.
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.
The positive divisors of 24 are 1, 2, 3,4, 6, 8,12, and 24.
The following relations hold:
If a|l, 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
so,
mg + nh = mbg1 + nbh1 = b × (mg1 + nh1)
and therefore b divides mg + nh.
b = 7; g = 14; h = 63; m = 3; n = 2
7 |14 and 7|63. To show 7|(3 × 14 + 2 ×63)
We have (3 ×14 + 2 ×63) = 7(3 × 2 + 2 ×9)
And it is obvious that 7| (7(3 ×2 + 2 ×9))
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 techniques discussed in this chapter.
Any integer a > 1 can be factored in a unique way as
a = p1a1 p2a2 p3a3…… ptai
where p1 > p2 > ... > pt are prime numbers and where each ai > 0.
91 = 7 ×13; 11011 = 7 ×112 ×13
It is useful for what follows 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 where each ap ≤ 0
p
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.
3600 = 24 ×32 ×52
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{.
Multiplication of two numbers is equivalent to adding the corresponding exponents:
k = mn → kp = mp + np for all p
k = 12 ×18=216
k2 = 2 + 1= 3; k3 = l + 2 = 3
216 = 23 ×33
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
a = 12; b = 36;12|36;12 = 22×3; 36 = 22×32
a2 = 2 = b2
a3 = 1 ≥ 2 = b3
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 |).
gcd(60, 24) = gcd(60, -24) = 12
Also, because all nonzero integers divide 0, we have gcd (a, 0) = |a | It is easy to determine the greatest common divisor of two positive integers if we express each integer as the product of primes.
300 = 22 ×31 ×52
18 = 21×32
gcd(18, 300) = 21 × 31 × 50 = 6
In general,
k = gcd(a, b) →k = 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.
2.2 Modular Arithmetic
Given any positive integer n and any integer a, if we divide a by n, we get a quotient
q and a 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.
a = 11; n = 7; 11 = 1 × 7 + 4; r = 4
a = -11; n = 7; -11= (-2) ×7 + 3; r = 3
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 at 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.
73 ≡ 4 mod 23; 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
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).
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
11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8=2
(11 + 15) mod 8 = 26 mod 8=2
[(11 mod 8) - (15 mod 8)] mod 8 = -4 mod 8=4
(11 - 15) mod 8 = -4 mod 8 = 4
[(11 mod 8) × (15 mod 8)] mod 8 = 21 mod 8 = 5
(11×15) mod 8 = 165 mod 8=5
Exponentiation is performed by repeated multiplication, as in ordinary arithmetic
To find 117 mod 13, we can proceed as follows:
112 ≡ 121≡ 4 mod 13
114 ≡ 42≡ 3 mod l3
117 ≡ 11×4×3≡ 132 ≡ 2mod 13
Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into modular arithmetic.
Table 2.1 provides an illustration of modular addition and multiplication modulo 8. Looking at addition, the results are straightforward and there is a regular pattern to the matrix. Also, as in ordinary addition, there is an additive inverse, or negative, to each number in modular arithmetic. In this case, the negative of a number x is the number y such that x + y = 0 mod 8. To find the additive inverse of a number in the left-hand column, scan across the corresponding row of the matrix to find the value 0; the number at the top of that column is the additive inverse; thus 2 + 6 = 0 mod 8, Similarly, the entries in the multiplication table are straightforward. In ordinary arithmetic, there is a multiplicative inverse, or reciprocal, to each number. In modular arithmetic mod 8, the multiplicative inverse of x is the number y such that x×y = 1 mod 8. Now, to find the multiplicative inverse of a number from the multiplication table, scan across the matrix in the row for that number to find the value 1; the number at the top of that column is the multiplicative inverse; thus 3×3=1 mod 8. Note that not all numbers mod 8 have a multiplicative inverse; we will discuss this later.
(a) Addition modulo 8
+ 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7 0
2 2 3 4 5 6 7 0 1
3 3 4 5 6 7 0 1 2
4 4 5 6 7 0 1 2 3
5 5 6 7 0 1 2 3 4
6 6 7 0 1 2 3 4 5
7 7 0 1 2 3 4 5 6
(b) Multiplication modulo 8
× 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 0 2 4 6
3 0 3 6 1 4 7 2 5
4 0 4 0 4 0 4 0 4
5 0 5 2 7 4 1 6 3
6 0 6 4 2 0 6 4 2
7 0 7 6 5 4 2 2 1
Table 2.1 Arithmetic Modulo 8
Properties of Modular Arithmetic, Define the set Zn as (he set of nonnegative integers less than n: Zn = {0,1,…. ,(n - 1)}
This is referred to as the set of residues modulo n, if we perform modular arithmetic within this set, the following properties hold for integers in Zn:
Property Expression
cumulative laws (w+x) mod n = (x+w)mod n
(w×x) mod n = (x×w)mod n
Associative laws [(w+x)+y]mod n = [w+(x+y)]mod n
[(w×x) ×y]mod n = [w×(x×y)]mod n
Distributive law Identities [(w×x) ×y]mod n = [(w×x)(w×y)]mod n
[(w+0)+y]mod n = w mod n
[(w×1) ×y]mod n = w mod n
Additive inverse (-w) For each w ∈ Zn there exists a Z such that w + z = 0 mod w
There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe that, as in ordinary arithmetic, we can write the following: if (a + b) ≡ (a + c) mod n then b ≡ c mod n (2.1)
(5 + 23) ≡ (5 + 7) mod 8; 23≡ 7 mod 8
Equation (2.1) is consistent with the existence of an additive inverse. Adding the additive inverse of a to both sides of Equation (2.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 it a is relatively prime to n (2.2)
To see this, consider an example in which the condition does not hold;
6×3 = 18 ≡ 2 mod 8
6×7 = 42 ≡ 2 mod 8
Yet 3 7 mod 8.
The reason for this strange result is that for any general modulus n, a multiplier a, when applied in turn to the numbers 0 through (n - 1), will fail to produce a complete set of residues if a and n have any factors in common.
with a = 6 and n = 8:
Z8 0 1 2 3 4 5 6 7
Multiply by 6 0 6 12 18 24 30 36 42
Residues 0 6 4 2 0 6 4 2
Because we do not have a complete set of residues when multiplying by 6, more than one number in Z8 maps into the same residue. Specifically, 6×0 mod 8 = 6×4 mod 8; 6×1 mod 8 = 6×5 mod 8; and so on. Because this is a many-to-one mapping, there is not a unique inverse to the multiply operation.
However, if we take a = 5 and n = 8,
Z8 0 1 2 3 4 5 6 7
Multiply by 5 0 5 10 15 20 25 30 35
Residues 0 5 2 7 4 1 6 3
The line of residues contains all the numbers in Z8, in a different order.
In general an integer has a multiplicative inverse in Zn if that integer is relatively prime to n
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 Theorem
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 (2.3)
Proof: From our previous discussion, we know that if all the elements of Zp are multiplied by a, modulo p, the result consists of the elements of Zp in some order. Furthermore, a × 0 = 0 mod p. Therefore, the (p - 1) numbers [a mod p, 2a mod p, ...., (p -1)a mod p] are just the numbers {1, 2, ...,(p - 1)} in some order. Multiply these numbers together:
( a × 2a × ... × (p - l)a) ≡ [(a mod p) ×(2a mod p) × ... × ((p - 1)a mod p)]mod p= (p – 1)! mod p
But a×2a×…×((p-1)a) = (p-1)! an-1
Therefore, (p-1)! an-1 = (p-1)! mod p
We can cancel the (p-1)! term because it is relatively prime to p [see Equation (2.2)], This yields Equation (2.3),
a = 7, p = 19
72 = 49 = 11 mod 19
74≡ 121≡ 7 mod 19
78 = 49 = 11 mod 19
716=121=7 mod l9
ap-1 - 718 = 716 × 72 ≡ 7 × 11 = 1 mod 19
An alternative form of the theorem is also useful: If p is prime and a is any positive integer, then
ap= a mod p (2.4)
p = 5, a = 3, 35 = 243 = 3 mod 5
p = 5, a = 10, 105 = 100000 = 10 mod 5 = 0 mod 5
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), where Ф (n), is the number of positive integers less than n and relatively prime to n.
Table 2.2 lists the first 30 values of Ф(n), The value Ф(l) is without meaning but is defined to have the value 1, It should be clear that for a prime number p,
Ф (P) = p - l
Now suppose that we have two prime numbers p and q. Then, for n = pq, Ф (n) = Ф (pq) = Ф (p) × Ф (q) = (p - 1) × (q - 1)
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
Table 2.2 Some Values of Euler's Totient Function Ф (n)
To see this, consider that the set of residues in Zn is {0, 1, ....(pq - l)}.The residues that are not relatively prime to n are the set {p, 2p. ..., (q - l)p], the set {q, 2q, ..., (p -1)q], and 0. Accordingly,
Ф (n) = pq – [(q-1)+(p-1)+1]
= pq – (p+q)+1
= (q-1) ×(p-1)
= Ф (p) ×Ф (q)
Ф (21) = 12= Ф (3) × Ф (7)= 2 × 6 = (3 - 1) × (7 - 1)
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 (2.5)
a = 3; n = 10; Ф (10) = 4; 34 = 81≡ 1 mod 10
a = 2; n = 11; Ф (11) =10; 210 = 1024 ≡ 1 mod 11
2.4 Testing for Primality
There is no simple yet efficient means of determining whether a large number is prime. In this section, we present one attractive approach. First, we need to derive some results. The first of these is as follows:
If p is an odd prime, then the equation
x2 ≡ 1 (mod p)
has only two solutions namely, x = 1 and x = -1.
Proof: We have x2- l = 0(mod p)
(x+ l)(x- l) = 0(mod p)
By the rules of modular arithmetic, the latter equality requires that p divide (x + 1) or p divide (x -1), or both. Suppose that p divides both (x + 1) and (x - 1). Then we can say that (x + 1) = kp and (x - 1) = jp for some integers k and j Subtracting the two equations yields 2 = (k- j)p. This equation can be true only for p = 2. By the terms of the theorem, we are concerned only with odd primes.
Therefore, for a given solution x, either p|(x+l)or p|(x-1) but not both. Suppose p|(x - 1). Then
x - 1 = kp for some k
Therefore, x ≡ 1 mod p. By similar reasoning we arrive at the other solution of x = - 1 mod p.
x2 ≡ 1 (mod 7) x2 = l (mod8)
12 = l mod7 12 = l mod 8
62 = 36mod7 = lmod7; 6= -l mod7 32 = 9mod8 = l mod 8
Solutions: 1, -1 52 = 25 mod 8 = 1 mod 8; 5 = -3 mod 8
72 = 49mod 8 = l mod 8; 7= -l mod8
Solutions: 1,-1, 3, -3
2.5 Euclid's Algorithm
One of the basic techniques of number theory is Euclid's algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers. An extended form of Euclid's algorithm determines the greatest common divisor of two positive integers and, if those numbers are relatively prime, the multiplicative inverse of one with respect to the other.
Finding the Greatest Common Divisor
Euclid's algorithm is based on the following theorem: For any nonnegative integer a and any positive integer b,
gcd(a, b) = gcd(b, a mod b) (2.6)
gcd (55,22) = gcd(22, 55 mod 22) = gcd(22,11) = 11
To see this, consider if d = gcd(a, b). Then, by the definition of gcd, d| a and d|b. For any positive integer b, a can be expressed in the form
a = kb + r = r mod b
a mod b = r
Therefore, (a mod b) = a - kb for some integer k. But because d|b, it also divides kb. We also have d|a. Therefore, d|(a mod b) This shows that d is a common divisor of b and (a mod b). Conversely, if d is a common divisor of b and (a mod b), then d|kb. and thus d| [kb + (a mod b)], which is equivalent to d\a. Thus, the set of common divisors of a and b is equal to the set of common divisors of b and (a mod b).
Therefore, the gcd of one is the same as the gcd of the other, proving the theorem. Equation (2.6) can be used repetitively to determine the greatest common divisor.
gcd(18,12) = gcd(12,6) = gcd(6,0) = 6
gcd(11,10) = gcd(10,1) = gcd(l, 0) = 1
Euclid's algorithm makes repeated use of Equation (2.6) to determine the greatest common divisor, as follows. The algorithm assumes d > f > 0, It is acceptable to restrict the algorithm to positive integers because gcd (a. b) = gcd (|a|, |b|).
EUCLID(d,f)
1. X← f; Y←d
1. if Y = 0 return X = gcd (d, f)
3. R = X mod Y
4. X← Y
5. Y←R
6, goto 2
To find the gcd(1970, 1066),
1970 = 1 × 1066 + 904 gcd(1066, 904)
1066 = 1 × 904 + 162 gcd(9Q4, 162)
904 = 5 × 162 + 94 gcd(1625 94)
162=1 ×94 + 68 gcd(94,68) .
94 = 1 × 68 + 26 gcd(68, 26)
68 = 2 × 26 + 16 gcd(26, 16)
26 = 1 × 16 + 10 gcd(16, 10)
16 = 1 × 10 + 6 gcd(10t6)
10 = 1 ×6 + 4 gcd(6,4)
6 = 2 × 2 + 2 gcd(4, 2)
2 = 2 × 2 + 0 gcd(2, 0)
Therefore, gcd(1970, 1066) = 2.
The alert reader may ask how we can be sure that this process terminates. That is, how can we be sure that at some point Y divides X? If not, we would get an endless sequence of positive integers, each one strictly smaller than the one before, and this is clearly impossible.
Finding the Multiplicative Inverse
If gcd(d,f) = 1, then d has a multiplicative inverse modulo f . that is for , positive integer d<f, there exists a d-1 < f such that d d-1 = 1 mod f. Euclid's algorithm can be extended so that, in addition to finding gcd (d,f), if the gcd is 1, the algorithm returns the multiplicative inverse of d.
Extended Euclid (m, b)
1. (A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 div B3
5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
Q A1 A2 A3 B1 B2 B3
- 1 0 1759 0 1 550
3 0 1 550 1 -3 109
5 1 -3 109 -5 16 5
21 -5 16 5 106 -339 4
1 106 -339 4 -111 355 1
Table 2.3 Inverse of 550 in modulo (1759)
| 