| Home / lib / tmp / | ||
Stein W. Elementary number theory and elliptic curves (web draft, Sept. 2004)(182s).pdf |
|
Size 1.2Mb Date Jan 10, 2006 |
2.1 Congruences Modulo n
In this section we define the ring Z/nZ of integers modulo n, introduce the Euler ϕ-function, and relate it to the multiplicative order of certain elements of Z/nZ. If a, b ∈ Z and n ∈ N, we say that a is congruent to b modulo n if n | a − b, and write a ≡ b (mod n). Let nZ = (n) be the ideal of Z generated by n. Definition 2.1.1 (Integers Mo dulo n). The ring of integers modulo n is the quotient ring Z/nZ of equivalence classes of integers modulo n. It is equipped with its natural ring structure: (a + nZ) + (b + nZ) = (a + b) + nZ (a + nZ) · (b + nZ) = (a · b) + nZ....
2.1.3 Wilson’s Theorem
The following characterization of prime numbers, from the 1770s, is called “Wilson’s Theorem”, though it was first proved by Lagrange. Prop osition 2.1.13 (Wilson’s Theorem). An integer p > 1 is prime if and only if (p − 1)! ≡ −1 (mod p). For example, if p = 3, then (p − 1)! = 2 ≡ −1 (mod 3). If p = 17, then (p − 1)! = 20922789888000 ≡ −1 But if p = 15, then (p − 1)! = 87178291200 ≡ 0 (mod 15), so 15 is composite. Thus Wilson’s theorem could be viewed as a primality test, though, from a computational point of view, it is probably the least efficient primality test since computing (n − 1)! takes so many steps. Proof. The statement is clear when p = 2, so henceforth we assume that p > 2. We first assume that p is prime and prove that (p − 1)! ≡ −1 (mod p). If a ∈ {1, 2, . . . , p − 1} then the equation ax ≡ 1 (mod p) (mod 17)....
since ϕ(pn ) is the number of numbers less than pn minus the number of those that are divisible by p. Thus, e.g., ϕ(389 · 112 ) = 388 · (112 − 11) = 388 · 110 = 42680....
2.5 The Structure of (Z/pZ)∗
This section is about the structure of the group (Z/pZ)∗ of units modulo a prime number p. The main result is that this group is always cyclic. We will use this result later in Chapter 4 in our proof of quadratic reciprocity. Definition 2.5.1 (Primitive ro ot). A primitive root modulo an integer n is an element of (Z/nZ)∗ of order ϕ(n). We will prove that there is a primitive root modulo every prime p. Since the unit group (Z/pZ)∗ has order p − 1, this implies that (Z/pZ)∗ is a cyclic group, a fact this will be extremely useful, since it completely determines the structure of (Z/pZ)∗ as an abelian group. If n is an odd prime power, then there is a primitive root modulo n (see Exercise 2.25), but there is no primitive root modulo the prime power 23 , and hence none mod 2n for n ≥ 3 (see Exercise 2.24). Section 2.5.1 is the key input to our proof that (Z/pZ)∗ is cyclic; here we show that for every divisor d of p − 1 there are exactly d elements of (Z/pZ)∗ whose order divides d. We then use this result in Section 2.5.2 to produce an element of (Z/pZ)∗ of order q r when q r is a prime power that exactly divides p − 1 (i.e., q r divides p − 1, but q r+1 does not divide p − 1), and multiply together these elements to obtain an element of (Z/pZ)∗ of order p − 1....
2.5.3 Artin’s Conjecture
Conjecture 2.5.11 (Emil Artin). Suppose a ∈ Z is not −1 or a perfect square. Then there are infinitely many primes p such that a is a primitive root modulo p. There is no single integer a such that Artin’s conjecture is known to be true. For any given a, Pieter [Mor93] proved that there are infinitely many p such that the order of a is divisible by the largest prime factor of p − 1. Hooley [Hoo67] proved that something called the Generalized Riemann Hypothesis implies Conjecture 2.5.11....
3.2.2 Encoding a Phrase in a Number
In order to use the RSA cryptosystem to encrypt messages, it is necessary to encode them as a sequence of numbers of size less than n = pq . We now describe a simple way to do this. For an implementation of a slightly more general encoding that includes extra randomness so that plain text encodes differently each time, see Section 7.3.2. Suppose s is a sequence of capital letters and spaces, and that s does not begin with a space. We encode s as a number in base 27 as follows: a single space corresponds to 0, the letter A to 1, B to 2, . . ., Z to 26. Thus “RUN NIKITA” is a number written in base 27: RUN NIKITA ↔ 279 · 18 + 278 · 21 + 277 · 14 + 276 · 0 + 275 · 14 + 274 · 9 + 273 · 11 + 272 · 9 + 27 · 20 + 1 = 143338425831991 (in decimal)....
and the output would be 3, 5, and 7. For computational exercises about cryptosystems, see the exercises for Chapter 7....
Proof. By Theorem 2.5.5, G = (Z/pZ)∗ is a cyclic group of order p − 1. Because p is odd, G has even order, so t=e subgroup H of squares of ah 1 if and only if a ∈ H , we elements of G has index 2 in G. Since p ∼ see that ψ is the composition G → G/H = {±1}, where we identify the nontrivial element of G/H with −1. Remark 4.1.4. We could also prove that ψ is surjective without using that (Z/pZ)∗ is cyclic, as follows. If a ∈ (Z/pZ)∗ is a square, say a ≡ b2 (mod p), then a(p−1)/2 = bp−1 ≡ 1 (mod p), so a is a root of f = x(p−1)/2 − 1. By Proposition 2.5.2, the polynomial f has at most (p − 1)/2 roots. Thus there must be an a ∈ (Z/pZ)∗ that is not a root of f , and for that a, we have a= ψ (a) = p −1, and trivially ψ (1) = 1, so the map ψ is surjective. Note...
To compute #(S ∩ I ), first rescale by a to see that , Z 1 #(S ∩ I ) = # ∩I a where 1 I= a p∪ , 2a a p 3 p 2p , 2a a ∪ ··· ∪ ( 2b − 1)p bp , 2a a ....
4.3.2 Proof of Quadratic Reciprocity
It is now straightforward to deduce the quadratic reciprocity law. First Proof of Theorem 4.1.5. First suppose that p ≡ q (mod 4). By swapping p and q if necessary, we may assume that p > q , and write p − q = 4a. Since p = 4a + q , =4 =4 a=a, p=4 a+q a q q q q q q and q = p − 4a p = − 4a p = − 1 p · a p ....
In order to prove the proposition, we introduce a few lemmas. Lemma 4.4.4. For any integer a, p p n−1 if a ≡ 0 (mod p), an ζ= 0 otherwise. =0...
(d) The map σ (a, b) = (b, a) that swaps coordinates is a bijection of the set S . It has exactly one fixed poia t if and only if there is n= an a ∈ Z/pZ such that 2a = 1 and p 1. Also, prove that a= 1 if and only if 2a = 1 has a solution a ∈ Z/pZ with p 2= 1. p (e) Finish by showing that σ has exactly one fixed point if and only if #S is odd, i.e., if and only if p ≡ ±1 (mod 8)....
| © 2007 eKnigu | ||