| 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.1.4 Quadratic Reciprocity
One of the most celebrated theorems of classical number theory is Gauss’s quadratic reciprocity law. One application is that it gives the following simple criterion for whether or not 5 is a square modulo an odd prime p: the number 5 is a perfect square modulo p if and only if p is congruent...
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.2.1 There Are Infinitely Many Primes
Note that each number on the left in the following table is prime. Does this pattern continue indefinitely? 3=2+1 7=2·3+1...
Proof. Suppose p1 , p2 , . . . , pn are primes of the form 4x − 1. Consider the number N = 4p1 p2 · · · pn − 1....
When gcd(a, n) = 1, then the equation ax ≡ b (mod n) may or may not have a solution. For example, 2x ≡ 1 (mod 4) has no solution, but 2x ≡ 2 (mod 4) does, and in fact it has more than one (x = 1 and x = 3). Generalizing Proposition 3.3.9 we obtain the following more general criterion for solvability....
3.3.3 Wilson’s Theorem
The following result, from the 1770s, is called “Wilson’s Theorem” (though it was first proved by Lagrange). Prop osition 3.3.15 (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), (mod 17)....
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....
PLAYING WITH FIRE On a mission to secure detonation chips from a terrorist organization’s heavily armed base camp, Nikita is captured as a hostage by the enemy. Or so it is made to look. Michael and Nikita have actually created the scenario in order to secretly rendezvous with each other. The ruse works, but when Birkoff [Section One’s master hacker] accidentally discovers encrypted messages between Michael and Nikita sent with Walter’s help, Birkoff is forced to tell Madeline. Suspecting that Michael and Nikita may be planning a coup d’tat, Operations and Madeline...
Here’s a very simple example with small numbers that illustrates what Michael and Nikita do. (They really used 200 digit numbers.) 1. p = 97, g = 5 2. n = 31 3. m = 95 4. ng ≡ 58 (mod 97) 5. mg ≡ 87 (mod 97) 6. s = nmg = 78 (mod 97) Nikita and Michael are foiled because everyone easily figures out s: 1. Everyone knows p, g , ng (mod p), and mg (mod p). 2. Using the very fast Euclidean algorithm, anyone can easily find a, b ∈ Z such that ag + bp = 1, which exist because gcd(g , p) = 1. 3. Then ang ≡ n (mod p), so everyone knows Nikita’s secret key n, and hence can find s just as easily as she did. To taunt her, Nikita’s captors give her the Math Review of Diffie and Hellman’s 1976 paper “New Directions in Cryptography”: “The authors discuss some recent results in communications theory [...] The first [method] has the feature that an unauthorized ‘eavesdropper’ will find it computationally infeasible to decipher the message [...] They propose a couple of techniques for implementing the system, but the reviewer was unconvinced.” Night darkens her cell as Nikita reflects on what has happened. Upon realizing that she misremembered how the system works, she phones Michael and they do the following: 1. Together Michael and Nikita choose a 200-digit (pseudo-)prime p and a number g with 1 < g < p....
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 )× ....
This chapter is about the structure of the group (Z/p)× of units modulo p. The main result is that this group is always cyclic. Definition 5.0.5 (Primitive ro ot). A primitive root modulo an integer n is an element of (Z/n)× of order ϕ(n). We prove that there is a primitive root modulo every prime p. Since (Z/p)× has order p − 1, this implies that (Z/p)× is a cyclic group, a fact this will be extremely useful, since it completely determines the structure of (Z/p)× as an abelian group. If n is an odd prime power, then there is also a primitive root modulo n (see the exercises), but there is no primitive root modulo the even prime power 23 . Section 5.1 is the key input in our proof that (Z/p)× is cyclic; here we show that for every divisor d of p − 1 there are exactly d elements of (Z/p)× whose order divides d. We then use this result in Section 5.2 to produce an element of (Z/p)× 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 combine together these to obtain an element of (Z/p)× of order p − 1....
Proof. This is a general fact about commuting elements of any finite group. Since (ab)rs = ars brs = 1,...
5.3 Artin’s Conjecture
Conjecture 5.3.1 (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 [47] proved that there are infinitely many p such that the order of a is divisible by the largest prime factor of p − 1. Hooley [32] proved that the Generalized Riemann Hypothesis implies Conjecture 5.3.1. This Generalized Riemann Hypothesis is, as its name suggests, a generalization of the Riemann Hypothesis; it asserts that certain functions, called “zeta functions”, have zeros only on the vertical line Re(s) = 1 . 2 Remark 5.3.2. Artin conjectured more precisely that if N (x, a) is the number of primes p ≤ x such that a is a primitive root modulo p, then N (x, a) is asymptotic to C (a)π (x), where C (a) is a positive constant that depends only on a and π (x) is the number of primes up to x....
| © 2007 eKnigu | ||