| Home / lib / tmp / | ||
Stein W. Elementary number theory and elliptic curves (web draft, June 2003)(251s).pdf |
|
Size 1.6Mb Date Jan 10, 2006 |
2.3 Notation and Conventions
We use the standard notation N, Z, Q, R, and C for the rings of natural, integer, rational, real, and complex numbers, respectively. We use the words proposition, theorem, lemma, corollary, etc., in their standard mathematical way. Thus usually a proposition is a routine assertion, a theorem a deeper culmination of ideas, a lemma something that will be used later to prove a proposition or theorem, and a corollary an easy consequence of a proposition, theorem, or lemma....
3.1.2 The Greatest Common Divisor
We will use the notion of greatest common divisor of two integers to prove that if p is a prime and p | ab, then p | a or p | b. This is the key step in our proof of Theorem 3.1.5. Definition 3.1.6. Let gcd(a, b) = max{d : d | a and d | b}, unless both a and b are 0 in which case gcd(0, 0) = 0. For example, gcd(1, 2) = 1, gcd(3, 27) = 3, and for any a, gcd(0, a) = gcd(a, 0) = a. The greatest common divisor of two numbers, even large numbers, is surprisingly easy to compute. For example, let’s compute gcd(2261, 1275). First, we recall the division algorithm, which you might recall from elementary school when you learned long division with remainder: Algorithm 3.1.7 (Division Algorithm). Suppose that a and b are natural numbers. Then there exist unique nonnegative integers q and r such that 0 ≤ r < b and a = bq + r. We use the division algorithm repeatedly to compute gcd(2261, 1275). Dividing 2261 by 1275 we find that 2261 = 1 · 1275 + 986,...
3.1.3 Numbers Factor as Products of Primes
In this section, we prove that every natural number factors as a product of primes. Then we discuss the difficulty of finding such a decomposition in practice. We will wait until Section 3.1.4 to prove that factorization is unique. As a first example, let n = 1275. Since 17 | 1275, n is definitely composite, n = 17 · 75. Next, 75 is 5 · 15 = 5 · 5 · 3, and we find that 1275 = 3 · 5 · 5 · 17. Generalizing this process proves the following proposition: Prop osition 3.1.12. Every natural number is a product of primes. Proof. Let n be a natural number. If n = 1, then n is the empty product of primes. If n is prime, we are done. If n is composite, then n = ab with a, b < n. By induction, a and b are products of primes, so n is also a product of primes. Two questions: is this factorization unique, and how quickly can we find a factorization? What if we had done something differently when breaking 1275 apart as a product of primes? Could the primes that show up be different? Let’s try: we have 1275 = 5 · 255. Now 255 = 5 · 51 and 51 = 17 · 3, so the factorization is the same, as asserted by Theorem 3.1.5 above. Regarding the second question, it is still unknown just how clever we can be at factoring. Op en Problem 3.1.13. Is there an algorithm which can factor any integer n in polynomial time? By “algorithm” we mean an algorithm in the sense of computer science, i.e., a sequence of instructions that can be run on a classical computer (Turing machine), which is guaranteed to terminate. By “polynomial time” we...
3.3 Congruences Modulo n
In this section we define the ring Z/n of integers modulo n, introduce the Euler ϕ-function , and relate it to the multiplicative order of certain elements of Z/n. Definition 3.3.1 (Congruence). Let a, b ∈ Z and n ∈ N. Then a is congruent to b modulo n if n | a − b. We write a ≡ b (mod n). In other words, a is congruent to b modulo n if we can get from a to b by adding or subtracting copies of n. For example, 13 ≡ 7 (mod 3), since 7 = 13 − 3 − 3, as illustrated in Figure 3.2. Congruence modulo n is an equivalence relation on Z (i.e., it is transitive, symmetric, and reflexive). Definition 3.3.2. The ring of integers modulo n is the set Z/n of equivalences classes of integers equipped with its natural ring structure. Example 3.3.3. Z/3 = {{. . . , −3, 0, 3, . . .}, {. . . , −2, 1, 4, . . .}, {. . . , −1, 2, 5, . . .}} We use the notation Z/n because Z/n is the quotient of the ring Z by the ideal nZ of multiples of n. Because Z/n is the quotient of a ring by an ideal, the ring structure on Z induces a ring structure on Z/n. We often let a denote the equivalence class of a, when this won’t cause confusion. If p is a prime Z/p is a field (see Exercise 16), which we sometimes also denote by Fp . It is very easy to derive tests for divisibility of an integer by 3, 5, 9, and 11 by working modulo n (see Exercise 12). For example,...
3.3.1 Linear Equations Modulo n
In this section, we are concerned with how to decide whether or not a linear equation of the form ax ≡ b (mod n) has a solution modulo n. For example, when a has a multiplicative inverse in Z/n then ax ≡ b (mod n) has a unique solution. Thus it is of interest to determine the units in Z/n, i.e., the elements which have a multiplicative inverse. Finding solutions to ax ≡ b (mod n) is the topic of Section 3.5. We will use complete sets of residues to prove that the units in Z/n are exactly the a ∈ Z/n such that gcd(a, n) = 1....
Prop osition 3.3.11. The equation ax ≡ b (mod n) has a solution if and only if gcd(a, n) divides b. Proof. Let g = gcd(a, n). If there is a solution x to the equation, then n | (ax − b). Since g | n and g | a, it follows that g | b....
Suppose a, n ∈ N with gcd(a, n) = 1. Then by Proposition 3.3.9 the equation ax ≡ 1 (mod n) has a unique solution. How can we find it? Prop osition 3.5.1. Suppose a, b ∈ Z and gcd(a, b) = d. Then there exists x, y ∈ Z such that ax + by = d. Remark 3.5.2. If e = cd is a multiple of d, then cax + cby = cd = e, so e can also be written in terms of a and b. We will not give a formal proof of Proposition 3.5.1, but instead we show how to find x and y in practice. To use this proposition to solve ax ≡ 1 (mod n), use that gcd(a, n) = 1 to find x and y such that ax + ny = 1. Then ax ≡ 1 (mod n). Suppose a = 5 and b = 7. The steps of the Euclidean gcd algorithm (Algorithm 3.1.8) are: 7=1·5+2 5=2·2+1 so 2 = 7 − 5 so 1 = 5 − 2 · 2 = 5 − 2(7 − 5) = 3 · 5 − 2 · 7...
3.5.4 A Polynomial Time Deterministic Primality Test
Though the practical method for deciding primality with high probability discussed above is very efficient in practice, it was for a long time an open problem to give an algorithm that decides whether or not any integer is prime in time bounded by a polynomial in the number of digits of the integer. Three Indian mathematicians, Agrawal, Kayal, and Saxena, recently found the first ever polynomial-time primality test. See [2] and also [5] for a concise exposition of their clever idea....
4.1.2 Realistic Diffie-Hel lman Example
In this section we present an example that uses bigger numbers. Let p = 93450983094850938450983409623 and g = −2 ∈ (Z/p)× , which has order p − 1. The secret random numbers generated by Nikita and Michael are n = 18319922375531859171613379181 and m = 82335836243866695680141440300. Nikita sends g n = 45416776270485369791375944998 ∈ (Z/q )× to Michael, and Michael sends g m = 15048074151770884271824225393 ∈ (Z/q )× to Nikita. They agree on the secret key g nm = 85771409470770521212346739540 ∈ (Z/q )× ....
| © 2007 eKnigu | ||