Podstrony
|
[ Pobierz całość w formacie PDF ]
That is, by (∗)
(∗∗)
xed ≡ x
(mod p).
Now we proved (∗∗) when gcd(x, p) = 1, but if gcd(x, p) = p it is obvious
since then x ≡ 0 (mod p). So in all cases (∗∗) holds. A similar argument
proves that for all x
xed ≡ x
(mod q).
So by Exercise 15.11, page 63, we have since gcd(p, q) =1
xed ≡ x
(mod m)
for all x.
Theorem 27.1. Let Jm = {0, 1, 2, . . . , m- 1} and define E : Jm → Jm by
E(x) =xe mod m
and D : Jm → Jm by
D(x) =xd mod m.
Then E and D are inverses of each other if m, e and d are as in Lemma
27.1.
115
Proof. It suffices to show that D(E(x)) = x for all x ∈ Jm. Let x ∈ Jm and
let E(x) =xe mod m = r1. Also let D (r1) =r1 mod m = r2. We must show
that r2 = x. Since xe mod m = r1 we know that
xe ≡ r1
(mod m).
Hence xed ≡ r1 (mod m). We also know that
r1 ≡ r2
(mod m).
Hence xed ≡ r2 (mod m). By Lemma 27.1 xed ≡ x (mod m) so we have
x ≡ r2
(mod m).
Since both x and r2 are in Jm we have by Exercise 15.5 that x = r2. This
completes the proof.
More details on the use of the RSA scheme will be given in the Maple
worksheets which are available from the course website which may be reached
from my home page: http://www.math.usf.edu/~eclark.
d
d
d
116
CHAPTER 27. THE RSA SCHEME
For more details you may download the free book
stract Algebra from my homepage:
http://www.math.usf.edu/~eclark
Appendix A
Rings and Groups
The material in this appendix is optional reading. However, for the sake
of completeness we state here the definition of a ring and the definition of
a group. If you are interested in learning more you might take the course
Elementary Abstract Algebra. Having had this course should make it a little
easier to understand the ideas in abstract algebra and vice versa.
Elementary Ab-
Alternatively, look in almost any book whose title contains the words Abstract
Algebra or Modern Algebra. Look for one with Introductory or Elementary
in the title.
Definition A.1. A ring is an ordered triple (R, +, ·) where R is a set and
+and · are binary operations on R satisfying the following properties:
A1 a +(b + c) =(a + b) +c for all a, b, c in R.
A2 a + b = b + a for all a, b in R.
A3 There is an element 0 ∈ R satisfying a +0=a for all a in R.
A4 For every a ∈ R there is an element b ∈ R such that a + b =0.
M1 a · (b · c) =(a · b) · c for all a, b, c in R.
D1 a · (b + c) =a · b + a · c for all a, b, c in R.
117
118
APPENDIX A. RINGS AND GROUPS
D2 (b + c) · a = b · a + c · a for all a, b, c in R.
Thus, to describe a ring one must specify three things:
1. a set,
2. a binary operation on the set called multiplication,
3. a binary operation on the set called addition.
Then, one must verify that the properties above are satisfied.
Example A.1. Here are some examples of rings. The two binary operations
+and · are in each case the ones that you are familiar with.
1. (R, +, ·)–the ring of real numbers.
2. (Q, +, ·)–the ring of rational numbers.
3. (Z, +, ·)–the ring of integers.
4. (Zn, +, ·)–the ring of integers modulo n.
5. (Mn(R), +, ·)–the ring of all n × n matrices over R.
Definition A.2. A group is an ordered pair (G, ∗) where G is a set and ∗
is a binary operation on G satisfying the following properties
1. x ∗ (y ∗ z) =(x ∗ y) ∗ z for all x, y, z in G.
2. There is an element e ∈ G satisfying e ∗ x = x and x ∗ e = x for all x
in G.
3. For each element x in G there is an element y in G satisfying x ∗ y = e
and y ∗ x = e.
Definition A.3. Agroup (G, ∗) is said to be Abelian if x ∗ y = y ∗ x for all
x, y ∈ G.
Thus, to describe a group one must specify two things:
1. a set, and
2. a binary operation on the set.
119
Then, one must verify that the binary operation is associative, that there is
an identity in the set, and that every element in the set has an inverse.
Example A.2. Here are some examples of groups. The binary operations
are in each case the ones that you are familiar with.
1. (Z, +) is a group with identity 0. The inverse of x ∈ Z is -x.
2. (Q, +) is a group with identity 0. The inverse of x ∈ Q is -x.
3. (R, +) is a group with identity 0. The inverse of x ∈ R is -x.
4. (Q -{0}, ·) is a group with identity 1. The inverse of x ∈ Q -{0} is
x-1.
5. (R -{0}, ·) is a group with identity 1. The inverse of x ∈ R -{0} is
x-1.
6. (Zn, +) is a group with identity 0. The inverse of x ∈ Zn is n - x if
x = 0, the inverse of 0 is 0.
7. (Un, ·) is a group with identity [1]. The inverse of [a] ∈ Un was shown
to exist in Chapter 22.
8. (Rn, +) where + is vector addition. The identity is the zero vector
(0, 0, . . . , 0) and the inverse of the vector x = (x1, x2, . . . , xn) is the
vector -x =(-x1, -x2, . . . , -xn).
9. (Mn(R), +). This is the group of all n × n matrices over R and + is
matrix addition.
120
APPENDIX A. RINGS AND GROUPS
Bibliography
[1] Tom Apostol, Introduction to Analytic Number Theory, Springer-Verlag,
New York-Heidelberg, 1976.
[2] Chris Caldwell, The Primes Pages,
http://www.utm.edu/research/primes/
[3] W. Edwin Clark, Number Theory Links,
http://www.math.usf.edu/~eclark/numtheory_links.html
[4] Earl Fife and Larry Husch, Number Theory (Mathematics Archives,
http://archives.math.utk.edu/topics/numberTheory.html
[ Pobierz całość w formacie PDF ]
zanotowane.pldoc.pisz.plpdf.pisz.plkskarol.keep.pl
|
