Groups, Rings, and Finite Fields. Andreas Klappenecker. September 12, 2002


 Antonia Lawrence
 3 years ago
 Views:
Transcription
1 Background on Groups, Rings, and Finite Fields Andreas Klappenecker September 12, 2002 A thorough understanding of the Agrawal, Kayal, and Saxena primality test requires some tools from algebra and elementary number theory. We collect here some basic definitions and facts. These notes cannot replace a standard text on algebra, but will hopefully provide enough background to make the beautiful result [1] accessible to a computer scientist. We provide numerous exercises so that the interested reader can gain a working knowledge in a short amount of time. Groups. A group is a set G which is equipped with a binary operation : G G G, such that i) the associative law (a b) c = a (b c) holds for all a, b, c G, ii) there exists an identity e G satisfying a e = e a = a for all a G, iii) each element a G has an inverse a 1 satisfying a 1 a = a a 1 = e. The prototype example of a group G is given by a set of invertible n n matrices with complex entries, such that G contains the identity matrix, is closed under matrix multiplication and matrix inversion. The composition is given by matrix multiplication, e is the identity matrix, and a 1 is the inverse matrix of a. The example illustrates that the group operation is not necessarily commutative, that is, in general a b will not be the same as b a. A group is called abelian if a b = b a holds for all a, b G. The number of elements in G is called the order of G. A group of finite order is said to be finite. X1 Construct a finite nonabelian group. An example of an abelian group is given by the set of integers Z with given by addition. Another example is given by the finite set Z/nZ = 1
2 {0, 1,, n 1}, where n > 1 is an integer and denotes addition of integers modulo n. The nonzero complex numbers C with given by multiplication is also an abelian group. X2 Is the set of nonnegative integers Z 0 with the usual addition a group? Let (G, ) be a group. A nonempty subset H of G such that x y H and x 1 H for all x, y H is called a subgroup of G. The subgroup H is apparently a group. The notation H G means that H is a subgroup of G. The set g H = {g h h H}, g G, is called a left coset of H in G. For example, the set G = Z/4Z = {0, 1, 2, 3} with addition modulo 4 is a group (with composition written as addition). The subset H = {0, 2} is a subgroup of G. The set 1 + H = {1, 3} is a coset of H in G. Notice that 0 + H = 2 + H and that 1 + H = 3 + H. X3 Let G be a group, H G. Show that H = g H for all g G. Show that either m H = n H or m H n H = holds for m, n G. X4 Let G be a finite group, H G. Prove that H divides G. We abbreviate the composition a a a of n times of a by a n. We write a n for the inverse of a n. It is understood that a 0 = e. The group operation is sometimes written additively a b = a + b. The identity element is then denoted by 0, the inverse of an element a by a, and a n is expressed by na. Let X be a subset of a group G. Then X denotes the smallest subgroup of G containing X, called the subgroup of G generated by X. Notice that X = {g a 1 1 g a l l g i X, a i Z, l Z, l 1}. A group G is called cyclic if and only if there exists an element a G such that G = a. For instance, the additive group of integers Z is a cyclic group generated by the element 1. Similarly, Z/nZ with addition modulo n is a cyclic group generated by 1. X5 Is the set Z Z with the usual composition (a, b) + (c, d) = (a + c, b + d) a cyclic group? Let G be a finite group. The order of an element g G is defined to be the smallest exponent such that g k = 1. The set {1, g, g 2,, g k 1 } coincides with the cyclic group g generated by g. It follows from X4 that the order of g must divide G. In particular, we have g G = 1 for all elements g G. 2
3 X6 Prove Fermat s Little Theorem: If p is a prime, and gcd(a, p) = 1, then a p 1 1 mod p. If p is a prime, then the subset (Z/pZ) of nonzero elements of Z/pZ forms a group under multiplication modulo p. Gauß proved that (Z/pZ) is a cyclic group. For instance, if p = 5, then (Z/pZ) = {1, 2, 3, 4} is generated by 2, since 2 = {2 0, 2 1, 2 2, 2 3 } = {1, 2, 4, 3}. Rings and Fields. A ring is a set R which is equipped with two binary operations, called addition and multiplication, such that i) R is an abelian group under addition, ii) multiplication is associative and posseses an identity element, iii) multiplication is distributive with respect to addition. We denote addition by a + b, and multiplication by juxtaposition ab. The identity element of addition is denoted by 0, and 1 denotes the identity element for multiplication. The ring R is said to be commutative if multiplication is commutative. A field is a commutative ring with 1 0 in which every nonzero element is invertible with respect to multiplication. X7 Explicitly state the axioms of a ring, a commutative ring, a field. X8 Determine whether the set of 2 2 matrices over the real numbers with matrix addition and matrix multiplication as binary operations is a ring, a commutative ring, a field. The set Z of integers with the usual addition and multiplication is an example of a commutative ring. The set Z/nZ = {0, 1,..., n 1} with addition modulo n and multiplication modulo n is another example of a commutative ring. X9 Show that ab = ac, a 0, does not necessarily imply b = c in a ring. Does this law hold in a field? X10 Show that Z/nZ is a field if and only if n is a prime. A polynomial over a commutative ring R is an ex Polynomial Rings. pression of the form f(x) = a n x n + + a 1 x + a 0, 3
4 where the coefficients a i, 0 i n, are elements of R and x is a variable with indeterminate meaning. The set of all such expressions is denoted by R[x]. The polynomial 0x m+n + + 0x n+1 + a n x n + + a 1 x + a 0 is regarded as the same polynomial as f(x). If a n 0, then n is called the degree of f(x), denoted by deg f(x). In this case a n = lc(f(x)) is called the leading coefficient of f(x). Let g(x) = b m x m + + b 1 x + b 0 be a polynomial in R[x]. Addition of polynomials is defined by f(x)+g(x) = b m x m + +b n+1 x n+1 +(a n +b n )x n + +(a 1 +b 1 )x+(a 0 +b 0 ), where we assumed without loss of generality that m n. The multiplication of polynomials is defined by f(x)g(x) = c m+n x m+n + + c 2 x 2 + c 1 x + c 0, where c k = a i b j. i+j=k X11 Let R be a commutative ring. Show that R[x] is a commutative ring. Let p be a prime. We denote by F p the finite field Z/pZ. The ring F p [x] has a Euclidean division with remainder. The consequence is that this ring resembles in many ways the ring of integers. X12 Let f, g F p [x] with g 0. Prove that there exist elements q, r F p [x] such that f(x) = q(x)g(x) + r(x), where r(x) = 0 or deg r(x) < deg g(x). Ideals. An ideal in a commutative ring R is an additive subgroup I of R such that if r R and s I, then rs I. An ideal I is said to be generated by a subset S I if and only if each element t I can be written in the form t = n i=1 r is i for some r i R and s i I. We denote the ideal generated by the subset S R by S. An ideal is said to be principal if and only if it can be generated by a single element in R. For example, in the ring Z of integers, the ideal 6, 15 is given by the set 6, 15 = {6n + 15m n, m Z} = {3m m Z}. X13 Prove that every ideal in F p [x] is a principal ideal. X14 Prove: if d(x) = a(x), b(x) in F p [x], then d(x) = gcd(a(x), b(x)). 4
5 Let I be an ideal of a commutative ring R. The cosets r + I, r R, form a partition of R, because I is in particular a subgroup of the additive group of R. Two elements a, b R are called congruent modulo I if and only if they belong to the same coset of I. We denote the congruence of a and b by a b mod I. In other words, a b mod I if and only if a b I. X15 Explain the meaning of a(x) b(x) mod n, x r 1 in Z[x]. X16 If a b mod I and c d mod I, then a+c b+d mod I and ac bd mod I. An ideal I of a commutative ring R allows to define a new ring, the residue class ring R/I. The elements of R/I are the cosets r + I of the ideal I. The addition and multiplication operations are respectively defined by (a + I) + (b + I) = (a + b) + I, (a + I)(b + I) = ab + I. The axioms of a commutative ring are easily verified for R/I. The prototype example is the ring Z of integers. An ideal in Z is of the form nz, since all ideals are principal in Z. The residue class ring Z/nZ gives then the usual modular arithmetic. Finite Fields. Fields with a finite number of elements find applications in algorithms of cryptography or coding theory, and in numerous number theoretic algorithms. We begin by looking at a few small fields. The arithmetic of the field F 2 = Z/2Z with two elements can be summarized by Similarly, the arithmetic of the finite field F 3 = Z/3Z is fully described by
6 A finite field with four element exists. However, we have convinced ourselves in exercise X10 that is cannot be of the form Z/4Z. The idea is to construct this field as a residue class ring of F 2 [x] modulo an ideal I. We already know that F = F 2 [x]/i is a commutative ring. We need to choose the ideal I such that each element r + I 0 + I of F is invertible, which means that there exists a residue class s + I such that (r + I)(s + I) = rs + I = 1 + I. Recall that an ideal in F p [x] is of the form h(x) by X13. A nonconstant polynomial in F p [x] is said to be irreducible if it cannot be written as a product of polynomials of postivie degree. X17 Let p be a prime, F p = Z/pZ, h(x) F p [x] with deg h(x) > 1. Show that the residue class ring F p [x]/ h(x) is a field if and only if h(x) is an irreducible polynomial in F p [x]. The construction of a finite field with four elements in now a simple matter. Note that the polynomial h(x) = x 2 + x + 1 is irreducible in F 2 [x]. The residue classes of F 2 [x]/ x 2 + x + 1 are given by the four elements 0 + x 2 + x + 1, 1 + x 2 + x + 1, x + x 2 + x + 1, 1 + x + x 2 + x + 1. For simplicity, we will calculate with the representatives 0, 1, x, 1 + x modulo the polynomial x 2 + x + 1 in F 2 [x]. The addition of the elements x and x + 1 yields 1 in F 2 [x]. The multiplication of x and x + 1 yields x(x + 1) = x 2 + x which is equivalent to 1 modulo x 2 + x + 1. Proceeding in this way, we can summarize the arithmetic rules of the field F 4 = F2 [x]/ x 2 + x + 1 by x 1 + x x 1 + x x x x x 1 + x x 1 + x x x 1 + x x 1 + x x 0 x 1 + x x x 1 x X18 Construct a finite field F 8 with 8 elements. A finite field F has always a subfield with a prime number of elements. This subfield F p is obtained by repeatedly adding the identity 1 of F to itself. The field F can be interpreted as a vector space over F p. It follows the number of elements of a finite field is a prime power. If dim Fp F = n, then F contains p n elements. 6
7 It can be shown that there exist irreducible polynomials in F p [x] of any given degree n. It turns out that any two fields with p n elements are isomorphic. Therefore, any finite field can be obtained by the residue class ring construction F p [x]/ h(x), which we have described above. It should be noted that the multiplicative group of nonzero elements of a finite field is always a cyclic group. For example, there exists a polynomial g(x) F p [x] such that any nonzero element f(x) + h(x) in the finite field F p [x]/ h(x) is of the form g(x) m + h(x) for some integer m. Final Remarks. There is of course much more that can be said about finite fields, rings, and groups. For a computer scientist, however, I would recommend to toy around with the ideas presented here. A computer algebra system is the perfect companion for further explorations. Good choices are GAP, MAGMA, Mathematica, or Maple. References [1] M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Preprint, IIT Kanpur, August [2] N. Jacobson. Basic Algebra I. W.H. Freeman and Company, New York, 2nd edition, Acknowledgments. Many thanks to Professor Jianer Chen, Avanti Ketkar, and Santosh Kumar for corrections and helpful comments. 7
8 Solutions S1 Let G be the set of invertible 2 2 matrices over the field with two elements F ( ) 2 ( = {0, 1}. ) The ( group ) contains ( ) six elements, and is nonabelian, since S2 No, since there is no integer a 0 such that 1 + a = 0. S3 Notice that x g x is a bijective mapping, thus H = g H. To prove the second statement, notice that there is nothing to prove if m H and n H are disjoint. Thus, let k m H and k n H. Thus, there exist h 1, h 2 H such that k = m h 1 = n h 2. Hence m h 1 h 1 2 = n, and m h 1 h 1 2 h = n h for all h H. Thus, n H m H. Similarly, m H n H. S4 By exercise X3, G is partitioned by the cosets of H, and all have the same size H. Thus G is a multiple of H. S5 No. If Z Z were generated by a single element (a, b), then all elements would be of the form (na, nb) for some n Z. It immediately follows that a and b have to equal 1, since the projection onto one coordinate must be Z. This would imply that the cyclic group just generates the diagonal of Z Z, contradiction. S6 We can regard a as an element of (Z/pZ). Note that gcd(a, p) = 1 and gcd(b, p) = 1 implies gcd(ab, p) = 1. We also have gcd(1, p) = 1. Since gcd(a, p) = 1 = ar + ps, we have that a 1 = r is a nonzero element in Z/pZ. Therefore, (Z/pZ) is a group, since it contains the identity 1, is closed under multiplication, and contains an inverse for each element. The order of this group is p 1, hence a p 1 = 1 in (Z/pZ). This proves the claim. S7 We can express the axioms of a ring by the following identities: a + (b + c) = (a + b) + c (associativity of addition) 0 + a = a + 0 (zero is the identity of addition) ( a) + a = a + ( a) = 0 (negative) a + b = b + a (commutativity of addition) a (b c) = (a b) c (associativity of multiplication) a 1 = 1 a = a (unit element) (a + b)c = ac + bc (left distributive law) a(b + c) = ab + ac (right distributive law) A commutative ring also satisfies ab = ba. A field is a commutative ring that satisfies 1 0 as well as a 1 a = aa 1 = 1 for all a 0. 8
9 S8 The multiplication of matrices is not commutative, thus the set it is not a commutative ring, in particular not a field. The usual rules for matrix addition and multiplication imply that the set is a ring. S9 Let Z/4Z. Then 2 2 = 2 0 = 0, but 2 0. In a field, the element a has an inverse a 1, implying b = a 1 (ab) = a 1 (bc) = c. S10 If n = 1, then 1 = 0 in Z/nZ, hence it is not a field. We may assume that n > 1. Suppose that n is composite, n = ab with a, b 1. Then ab = a0 but b 0, because n > 1. Since this cancellation law does not hold, Z/nZ cannot be a field by exercise X9. If p is a prime, then Z/pZ is a commutative ring in which 1 0 and every element a 0 has a multiplicative inverse (which can be found using the extended Euclidean algorithm), hence Z/pZ is a field. S11 Routine verification, see Section 2.10 in [2]. S12 Let n = deg f(x), m = deg g(x), and α = lc(f(x)), β = lc(g(x)). We prove the result by induction on n. If n < m, then q(x) = 0 and r(x) = f(x) does the job. If n m, then the polynomial f 0 (x) = f(x) αβ 1 x n m g(x) has degree smaller than f(x). By induction, there exist polynomials q 0 (x), r 0 (x) such that f 0 (x) = q 0 (x)g(x) + r 0 (x) with r 0 (x) = 0 or deg r 0 (x) < deg g(x). Let q(x) = αβ 1 x n m + q 0 (x) and r(x) = r 0 (x). This choice gives f(x) = q(x)g(x) + r(x), as desired. S13 Let I be a ideal in F p [x]. If I = 0, then we are done. If not, then I must contain a nonzero element. Choose an element s(x) 0 of I of minimal degree. If t(x) is an arbitrary element of I, then t(x) = q(x)s(x) + r(x) with r(x) = 0 or deg r(x) < deg s(x). Suppose that r(x) 0, which means that deg r(x) < deg s(x). Since s(x), t(x) I, we have r(x) = t(x) q(x)s(x) I. However, r(x) is of smaller degree than s(x), contradiction. Therefore, r(x) = 0, and we can conclude that all elements in the ideal I are multiples of s(x), that is, I = s(x). S14 We have a(x) = g(x)d(x) and b(x) = h(x)d(x), since a(x), b(x) d(x). Hence d(x) is a common divisor of a(x) and b(x). Since d(x) a(x), b(x), we have d(x) = a(x)r(s) + b(x)s(x) for some r(x), s(x) F p [x]. Thus, any common divisor of a(x) and b(x) must divide d(x). S15 The notation means that there exist polynomials g(x), h(x) Z[x] such that a(x) b(x) = ng(x) + (x r 1)h(x), that is, a(x) = b(x) + ng(x) + (x r 1)h(x). S16 By assumption, a b and c d are elements of I. Thus (a b) + (c d) = (a + c) (b + d) I, which shows that a + c b + d mod I. Moreover, (a b)c and 9
10 b(c d) are elements of I, hence (a b)c + b(c d) = ac bd I, which proves ac bd mod I. S17 The nonzero elements of F p [x]/ h(x) can be assumed to be of the form g(x) + h(x) with g(x) 0 and deg g(x) < deg h(x). If h(x) is irreducible, then gcd(g(x), h(x)) = 1 = g(x)r(x) + h(x)s(x) for some polynomials r(x), s(x) F p [x] by exercise X13. Hence, r(x) is the inverse of g(x) modulo h(x). It follows that F p [x]/ h(x) is a finite field provided that h(x) is irreducible. On the other hand, if h(x) is reducible, then there exist polynomials f(x), g(x) F p [x] of degree > 1 such that h(x) = f(x)g(x). Note that g(x)0 = g(x)f(x) in F p [x]/ h(x) does not imply f(x) = 0, hence the cancellation law does not hold, whence F p [x]/ h(x) cannot be a field by exercise X9. S18 The polynomial h(x) = x 3 + x is irreducible in F 2 [x]. The field is given by F 2 [x]/ h(x). We leave the construction of addition and multiplication table to the reader. 10
LECTURE NOTES IN CRYPTOGRAPHY
1 LECTURE NOTES IN CRYPTOGRAPHY Thomas Johansson 2005/2006 c Thomas Johansson 2006 2 Chapter 1 Abstract algebra and Number theory Before we start the treatment of cryptography we need to review some basic
More informationIntroduction to finite fields
Chapter 7 Introduction to finite fields This chapter provides an introduction to several kinds of abstract algebraic structures, particularly groups, fields, and polynomials. Our primary interest is in
More informationFoundations of Cryptography
Foundations of Cryptography Ville Junnila viljun@utu.fi Department of Mathematics and Statistics University of Turku 2015 Ville Junnila viljun@utu.fi Lecture 7 1 of 18 Cosets Definition 2.12 Let G be a
More informationMathematics for Cryptography
Mathematics for Cryptography Douglas R. Stinson David R. Cheriton School of Computer Science University of Waterloo Waterloo, Ontario, N2L 3G1, Canada March 15, 2016 1 Groups and Modular Arithmetic 1.1
More informationCHAPTER 14. Ideals and Factor Rings
CHAPTER 14 Ideals and Factor Rings Ideals Definition (Ideal). A subring A of a ring R is called a (twosided) ideal of R if for every r 2 R and every a 2 A, ra 2 A and ar 2 A. Note. (1) A absorbs elements
More informationPublickey Cryptography: Theory and Practice
Publickey Cryptography Theory and Practice Department of Computer Science and Engineering Indian Institute of Technology Kharagpur Chapter 2: Mathematical Concepts Divisibility Congruence Quadratic Residues
More informationRings. Chapter 1. Definition 1.2. A commutative ring R is a ring in which multiplication is commutative. That is, ab = ba for all a, b R.
Chapter 1 Rings We have spent the term studying groups. A group is a set with a binary operation that satisfies certain properties. But many algebraic structures such as R, Z, and Z n come with two binary
More informationChapter 4 Finite Fields
Chapter 4 Finite Fields Introduction will now introduce finite fields of increasing importance in cryptography AES, Elliptic Curve, IDEA, Public Key concern operations on numbers what constitutes a number
More informationMTH310 EXAM 2 REVIEW
MTH310 EXAM 2 REVIEW SA LI 4.1 Polynomial Arithmetic and the Division Algorithm A. Polynomial Arithmetic *Polynomial Rings If R is a ring, then there exists a ring T containing an element x that is not
More informationCHAPTER I. Rings. Definition A ring R is a set with two binary operations, addition + and
CHAPTER I Rings 1.1 Definitions and Examples Definition 1.1.1. A ring R is a set with two binary operations, addition + and multiplication satisfying the following conditions for all a, b, c in R : (i)
More informationFinite Fields. Mike Reiter
1 Finite Fields Mike Reiter reiter@cs.unc.edu Based on Chapter 4 of: W. Stallings. Cryptography and Network Security, Principles and Practices. 3 rd Edition, 2003. Groups 2 A group G, is a set G of elements
More informationMath 2070BC Term 2 Weeks 1 13 Lecture Notes
Math 2070BC 2017 18 Term 2 Weeks 1 13 Lecture Notes Keywords: group operation multiplication associative identity element inverse commutative abelian group Special Linear Group order infinite order cyclic
More information(Rgs) Rings Math 683L (Summer 2003)
(Rgs) Rings Math 683L (Summer 2003) We will first summarise the general results that we will need from the theory of rings. A unital ring, R, is a set equipped with two binary operations + and such that
More informationMathematical Foundations of Cryptography
Mathematical Foundations of Cryptography Cryptography is based on mathematics In this chapter we study finite fields, the basis of the Advanced Encryption Standard (AES) and elliptical curve cryptography
More informationNOTES ON FINITE FIELDS
NOTES ON FINITE FIELDS AARON LANDESMAN CONTENTS 1. Introduction to finite fields 2 2. Definition and constructions of fields 3 2.1. The definition of a field 3 2.2. Constructing field extensions by adjoining
More informationFinite Fields. Saravanan Vijayakumaran Department of Electrical Engineering Indian Institute of Technology Bombay
1 / 25 Finite Fields Saravanan Vijayakumaran sarva@ee.iitb.ac.in Department of Electrical Engineering Indian Institute of Technology Bombay September 25, 2014 2 / 25 Fields Definition A set F together
More informationLecture 7: Polynomial rings
Lecture 7: Polynomial rings Rajat Mittal IIT Kanpur You have seen polynomials many a times till now. The purpose of this lecture is to give a formal treatment to constructing polynomials and the rules
More informationA field F is a set of numbers that includes the two numbers 0 and 1 and satisfies the properties:
Byte multiplication 1 Field arithmetic A field F is a set of numbers that includes the two numbers 0 and 1 and satisfies the properties: F is an abelian group under addition, meaning  F is closed under
More informationFinite Fields. Sophie Huczynska. Semester 2, Academic Year
Finite Fields Sophie Huczynska Semester 2, Academic Year 200506 2 Chapter 1. Introduction Finite fields is a branch of mathematics which has come to the fore in the last 50 years due to its numerous applications,
More informationAlgebra Homework, Edition 2 9 September 2010
Algebra Homework, Edition 2 9 September 2010 Problem 6. (1) Let I and J be ideals of a commutative ring R with I + J = R. Prove that IJ = I J. (2) Let I, J, and K be ideals of a principal ideal domain.
More informationRINGS: SUMMARY OF MATERIAL
RINGS: SUMMARY OF MATERIAL BRIAN OSSERMAN This is a summary of terms used and main results proved in the subject of rings, from Chapters 1113 of Artin. Definitions not included here may be considered
More informationSection 18 Rings and fields
Section 18 Rings and fields Instructor: Yifan Yang Spring 2007 Motivation Many sets in mathematics have two binary operations (and thus two algebraic structures) For example, the sets Z, Q, R, M n (R)
More informationOutline. MSRIUP 2009 Coding Theory Seminar, Week 2. The definition. Link to polynomials
Outline MSRIUP 2009 Coding Theory Seminar, Week 2 John B. Little Department of Mathematics and Computer Science College of the Holy Cross Cyclic Codes Polynomial Algebra More on cyclic codes Finite fields
More information0 Sets and Induction. Sets
0 Sets and Induction Sets A set is an unordered collection of objects, called elements or members of the set. A set is said to contain its elements. We write a A to denote that a is an element of the set
More informationSchool of Mathematics and Statistics. MT5836 Galois Theory. Handout 0: Course Information
MRQ 2017 School of Mathematics and Statistics MT5836 Galois Theory Handout 0: Course Information Lecturer: Martyn Quick, Room 326. Prerequisite: MT3505 (or MT4517) Rings & Fields Lectures: Tutorials: Mon
More informationAlgebra Review. Instructor: Laszlo Babai Notes by Vincent Lucarelli and the instructor. June 15, 2001
Algebra Review Instructor: Laszlo Babai Notes by Vincent Lucarelli and the instructor June 15, 2001 1 Groups Definition 1.1 A semigroup (G, ) is a set G with a binary operation such that: Axiom 1 ( a,
More informationMATH 433 Applied Algebra Lecture 4: Modular arithmetic (continued). Linear congruences.
MATH 433 Applied Algebra Lecture 4: Modular arithmetic (continued). Linear congruences. Congruences Let n be a postive integer. The integers a and b are called congruent modulo n if they have the same
More informationMath Introduction to Modern Algebra
Math 343  Introduction to Modern Algebra Notes Rings and Special Kinds of Rings Let R be a (nonempty) set. R is a ring if there are two binary operations + and such that (A) (R, +) is an abelian group.
More informationFinite Fields and ErrorCorrecting Codes
Lecture Notes in Mathematics Finite Fields and ErrorCorrecting Codes KarlGustav Andersson (Lund University) (version 1.01316 September 2015) Translated from Swedish by Sigmundur Gudmundsson Contents
More informationChapter 3. Rings. The basic commutative rings in mathematics are the integers Z, the. Examples
Chapter 3 Rings Rings are additive abelian groups with a second operation called multiplication. The connection between the two operations is provided by the distributive law. Assuming the results of Chapter
More informationCoding Theory ( Mathematical Background I)
N.L.Manev, Lectures on Coding Theory (Maths I) p. 1/18 Coding Theory ( Mathematical Background I) Lector: Nikolai L. Manev Institute of Mathematics and Informatics, Sofia, Bulgaria N.L.Manev, Lectures
More informationElementary Algebra Chinese Remainder Theorem Euclidean Algorithm
Elementary Algebra Chinese Remainder Theorem Euclidean Algorithm April 11, 2010 1 Algebra We start by discussing algebraic structures and their properties. This is presented in more depth than what we
More informationSolutions to oddnumbered exercises Peter J. Cameron, Introduction to Algebra, Chapter 2
Solutions to oddnumbered exercises Peter J Cameron, Introduction to Algebra, Chapter 1 The answers are a No; b No; c Yes; d Yes; e No; f Yes; g Yes; h No; i Yes; j No a No: The inverse law for addition
More informationU + V = (U V ) (V U), UV = U V.
Solution of Some Homework Problems (3.1) Prove that a commutative ring R has a unique 1. Proof: Let 1 R and 1 R be two multiplicative identities of R. Then since 1 R is an identity, 1 R = 1 R 1 R. Since
More informationMT5836 Galois Theory MRQ
MT5836 Galois Theory MRQ May 3, 2017 Contents Introduction 3 Structure of the lecture course............................... 4 Recommended texts..................................... 4 1 Rings, Fields and
More informationAlgebraic structures I
MTH5100 Assignment 110 Algebraic structures I For handing in on various dates January March 2011 1 FUNCTIONS. Say which of the following rules successfully define functions, giving reasons. For each one
More informationCourse 311: Michaelmas Term 2005 Part III: Topics in Commutative Algebra
Course 311: Michaelmas Term 2005 Part III: Topics in Commutative Algebra D. R. Wilkins Contents 3 Topics in Commutative Algebra 2 3.1 Rings and Fields......................... 2 3.2 Ideals...............................
More informationChapter 5. Modular arithmetic. 5.1 The modular ring
Chapter 5 Modular arithmetic 5.1 The modular ring Definition 5.1. Suppose n N and x, y Z. Then we say that x, y are equivalent modulo n, and we write x y mod n if n x y. It is evident that equivalence
More information2a 2 4ac), provided there is an element r in our
MTH 310002 Test II Review Spring 2012 Absractions versus examples The purpose of abstraction is to reduce ideas to their essentials, uncluttered by the details of a specific situation Our lectures built
More informationAbstract Algebra, Second Edition, by John A. Beachy and William D. Blair. Corrections and clarifications
1 Abstract Algebra, Second Edition, by John A. Beachy and William D. Blair Corrections and clarifications Note: Some corrections were made after the first printing of the text. page 9, line 8 For of the
More informationPart IX. Factorization
IX.45. Unique Factorization Domains 1 Part IX. Factorization Section IX.45. Unique Factorization Domains Note. In this section we return to integral domains and concern ourselves with factoring (with respect
More informationABSTRACT ALGEBRA MODULUS SPRING 2006 by Jutta Hausen, University of Houston
ABSTRACT ALGEBRA MODULUS SPRING 2006 by Jutta Hausen, University of Houston Undergraduate abstract algebra is usually focused on three topics: Group Theory, Ring Theory, and Field Theory. Of the myriad
More informationModern Computer Algebra
Modern Computer Algebra Exercises to Chapter 25: Fundamental concepts 11 May 1999 JOACHIM VON ZUR GATHEN and JÜRGEN GERHARD Universität Paderborn 25.1 Show that any subgroup of a group G contains the neutral
More informationa b (mod m) : m b a with a,b,c,d real and ad bc 0 forms a group, again under the composition as operation.
Homework for UTK M351 Algebra I Fall 2013, Jochen Denzler, MWF 10:10 11:00 Each part separately graded on a [0/1/2] scale. Problem 1: Recalling the field axioms from class, prove for any field F (i.e.,
More informationCongruences and Residue Class Rings
Congruences and Residue Class Rings (Chapter 2 of J. A. Buchmann, Introduction to Cryptography, 2nd Ed., 2004) Shoichi Hirose Faculty of Engineering, University of Fukui S. Hirose (U. Fukui) Congruences
More informationAlgebra Review 2. 1 Fields. A field is an extension of the concept of a group.
Algebra Review 2 1 Fields A field is an extension of the concept of a group. Definition 1. A field (F, +,, 0 F, 1 F ) is a set F together with two binary operations (+, ) on F such that the following conditions
More information1. Factorization Divisibility in Z.
8 J. E. CREMONA 1.1. Divisibility in Z. 1. Factorization Definition 1.1.1. Let a, b Z. Then we say that a divides b and write a b if b = ac for some c Z: a b c Z : b = ac. Alternatively, we may say that
More informationEighth Homework Solutions
Math 4124 Wednesday, April 20 Eighth Homework Solutions 1. Exercise 5.2.1(e). Determine the number of nonisomorphic abelian groups of order 2704. First we write 2704 as a product of prime powers, namely
More informationMATH 361: NUMBER THEORY FOURTH LECTURE
MATH 361: NUMBER THEORY FOURTH LECTURE 1. Introduction Everybody knows that three hours after 10:00, the time is 1:00. That is, everybody is familiar with modular arithmetic, the usual arithmetic of the
More informationSection 19 Integral domains
Section 19 Integral domains Instructor: Yifan Yang Spring 2007 Observation and motivation There are rings in which ab = 0 implies a = 0 or b = 0 For examples, Z, Q, R, C, and Z[x] are all such rings There
More informationA connection between number theory and linear algebra
A connection between number theory and linear algebra Mark Steinberger Contents 1. Some basics 1 2. Rational canonical form 2 3. Prime factorization in F[x] 4 4. Units and order 5 5. Finite fields 7 6.
More informationMoreover this binary operation satisfies the following properties
Contents 1 Algebraic structures 1 1.1 Group........................................... 1 1.1.1 Definitions and examples............................. 1 1.1.2 Subgroup.....................................
More informationRings. Chapter Definitions and Examples
Chapter 5 Rings Nothing proves more clearly that the mind seeks truth, and nothing reflects more glory upon it, than the delight it takes, sometimes in spite of itself, in the driest and thorniest researches
More informationFactorization in Polynomial Rings
Factorization in Polynomial Rings Throughout these notes, F denotes a field. 1 Long division with remainder We begin with some basic definitions. Definition 1.1. Let f, g F [x]. We say that f divides g,
More information76 CHAPTER 7. INTRODUCTION TO FINITE FIELDS For further reading on this beautiful subject, see [E. R. Berlekamp, Algebraic Coding Theory, Aegean Press
Chapter 7 Introduction to finite fields This chapter provides an introduction to several kinds of abstract algebraic structures, particularly groups, fields, and polynomials. Our primary interest is in
More informationφ(xy) = (xy) n = x n y n = φ(x)φ(y)
Groups 1. (Algebra Comp S03) Let A, B and C be normal subgroups of a group G with A B. If A C = B C and AC = BC then prove that A = B. Let b B. Since b = b1 BC = AC, there are a A and c C such that b =
More informationBasic elements of number theory
Cryptography Basic elements of number theory Marius Zimand By default all the variables, such as a, b, k, etc., denote integer numbers. Divisibility a 0 divides b if b = a k for some integer k. Notation
More informationModular Arithmetic and Elementary Algebra
18.310 lecture notes September 2, 2013 Modular Arithmetic and Elementary Algebra Lecturer: Michel Goemans These notes cover basic notions in algebra which will be needed for discussing several topics of
More informationBasic elements of number theory
Cryptography Basic elements of number theory Marius Zimand 1 Divisibility, prime numbers By default all the variables, such as a, b, k, etc., denote integer numbers. Divisibility a 0 divides b if b = a
More informationComputations/Applications
Computations/Applications 1. Find the inverse of x + 1 in the ring F 5 [x]/(x 3 1). Solution: We use the Euclidean Algorithm: x 3 1 (x + 1)(x + 4x + 1) + 3 (x + 1) 3(x + ) + 0. Thus 3 (x 3 1) + (x + 1)(4x
More informationKevin James. MTHSC 412 Section 3.1 Definition and Examples of Rings
MTHSC 412 Section 3.1 Definition and Examples of Rings A ring R is a nonempty set R together with two binary operations (usually written as addition and multiplication) that satisfy the following axioms.
More informationFinite Fields. Sophie Huczynska (with changes by Max Neunhöffer) Semester 2, Academic Year 2012/13
Finite Fields Sophie Huczynska (with changes by Max Neunhöffer) Semester 2, Academic Year 2012/13 Contents 1 Introduction 3 1 Group theory: a brief summary............................ 3 2 Rings and fields....................................
More informationMATH 403 MIDTERM ANSWERS WINTER 2007
MAH 403 MIDERM ANSWERS WINER 2007 COMMON ERRORS (1) A subset S of a ring R is a subring provided that x±y and xy belong to S whenever x and y do. A lot of people only said that x + y and xy must belong
More informationCOMPUTER ARITHMETIC. 13/05/2010 cryptography  math background pp. 1 / 162
COMPUTER ARITHMETIC 13/05/2010 cryptography  math background pp. 1 / 162 RECALL OF COMPUTER ARITHMETIC computers implement some types of arithmetic for instance, addition, subtratction, multiplication
More informationALGEBRA PH.D. QUALIFYING EXAM September 27, 2008
ALGEBRA PH.D. QUALIFYING EXAM September 27, 2008 A passing paper consists of four problems solved completely plus significant progress on two other problems; moreover, the set of problems solved completely
More informationSection IV.23. Factorizations of Polynomials over a Field
IV.23 Factorizations of Polynomials 1 Section IV.23. Factorizations of Polynomials over a Field Note. Our experience with classical algebra tells us that finding the zeros of a polynomial is equivalent
More information50 Algebraic Extensions
50 Algebraic Extensions Let E/K be a field extension and let a E be algebraic over K. Then there is a nonzero polynomial f in K[x] such that f(a) = 0. Hence the subset A = {f K[x]: f(a) = 0} of K[x] does
More informationPolynomial Rings. (Last Updated: December 8, 2017)
Polynomial Rings (Last Updated: December 8, 2017) These notes are derived primarily from Abstract Algebra, Theory and Applications by Thomas Judson (16ed). Most of this material is drawn from Chapters
More informationAbstract Algebra: Chapters 16 and 17
Study polynomials, their factorization, and the construction of fields. Chapter 16 Polynomial Rings Notation Let R be a commutative ring. The ring of polynomials over R in the indeterminate x is the set
More informationPolynomials. Chapter 4
Chapter 4 Polynomials In this Chapter we shall see that everything we did with integers in the last Chapter we can also do with polynomials. Fix a field F (e.g. F = Q, R, C or Z/(p) for a prime p). Notation
More informationDMATH Algebra I HS 2013 Prof. Brent Doran. Exercise 11. Rings: definitions, units, zero divisors, polynomial rings
DMATH Algebra I HS 2013 Prof. Brent Doran Exercise 11 Rings: definitions, units, zero divisors, polynomial rings 1. Show that the matrices M(n n, C) form a noncommutative ring. What are the units of M(n
More information* 8 Groups, with Appendix containing Rings and Fields.
* 8 Groups, with Appendix containing Rings and Fields Binary Operations Definition We say that is a binary operation on a set S if, and only if, a, b, a b S Implicit in this definition is the idea that
More informationMATH 3030, Abstract Algebra FALL 2012 Toby Kenney Midyear Examination Friday 7th December: 7:0010:00 PM
MATH 3030, Abstract Algebra FALL 2012 Toby Kenney Midyear Examination Friday 7th December: 7:0010:00 PM Basic Questions 1. Compute the factor group Z 3 Z 9 / (1, 6). The subgroup generated by (1, 6) is
More informationRings. EE 387, Notes 7, Handout #10
Rings EE 387, Notes 7, Handout #10 Definition: A ring is a set R with binary operations, + and, that satisfy the following axioms: 1. (R, +) is a commutative group (five axioms) 2. Associative law for
More information5.1 Commutative rings; Integral Domains
5.1 J.A.Beachy 1 5.1 Commutative rings; Integral Domains from A Study Guide for Beginner s by J.A.Beachy, a supplement to Abstract Algebra by Beachy / Blair 23. Let R be a commutative ring. Prove the following
More informationHonors Algebra 4, MATH 371 Winter 2010 Assignment 3 Due Friday, February 5 at 08:35
Honors Algebra 4, MATH 371 Winter 2010 Assignment 3 Due Friday, February 5 at 08:35 1. Let R 0 be a commutative ring with 1 and let S R be the subset of nonzero elements which are not zero divisors. (a)
More information1. multiplication is commutative and associative;
Chapter 4 The Arithmetic of Z In this chapter, we start by introducing the concept of congruences; these are used in our proof (going back to Gauss 1 ) that every integer has a unique prime factorization.
More informationCSIR  Algebra Problems
CSIR  Algebra Problems N. Annamalai DST  INSPIRE Fellow (SRF) Department of Mathematics Bharathidasan University Tiruchirappalli 620024 Email: algebra.annamalai@gmail.com Website: https://annamalaimaths.wordpress.com
More informationECEN 5022 Cryptography
Elementary Algebra and Number Theory University of Colorado Spring 2008 Divisibility, Primes Definition. N denotes the set {1, 2, 3,...} of natural numbers and Z denotes the set of integers {..., 2, 1,
More informationReducibility of Polynomials over Finite Fields
Master Thesis Reducibility of Polynomials over Finite Fields Author: Muhammad Imran Date: 19760602 Subject: Mathematics Level: Advance Course code: 5MA12E Abstract Reducibility of certain class of polynomials
More informationAlgebra Exam Fall Alexander J. Wertheim Last Updated: October 26, Groups Problem Problem Problem 3...
Algebra Exam Fall 2006 Alexander J. Wertheim Last Updated: October 26, 2017 Contents 1 Groups 2 1.1 Problem 1..................................... 2 1.2 Problem 2..................................... 2
More informationRings and groups. Ya. Sysak
Rings and groups. Ya. Sysak 1 Noetherian rings Let R be a ring. A (right) R module M is called noetherian if it satisfies the maximum condition for its submodules. In other words, if M 1... M i M i+1...
More informationAlgebra Qualifying Exam August 2001 Do all 5 problems. 1. Let G be afinite group of order 504 = 23 32 7. a. Show that G cannot be isomorphic to a subgroup of the alternating group Alt 7. (5 points) b.
More informationIntroduction to Information Security
Introduction to Information Security Lecture 5: Number Theory 007. 6. Prof. Byoungcheon Lee sultan (at) joongbu. ac. kr Information and Communications University Contents 1. Number Theory Divisibility
More informationTotal 100
Math 542 Midterm Exam, Spring 2016 Prof: Paul Terwilliger Your Name (please print) SOLUTIONS NO CALCULATORS/ELECTRONIC DEVICES ALLOWED. MAKE SURE YOUR CELL PHONE IS OFF. Problem Value 1 10 2 10 3 10 4
More information2 ALGEBRA II. Contents
ALGEBRA II 1 2 ALGEBRA II Contents 1. Results from elementary number theory 3 2. Groups 4 2.1. Denition, Subgroup, Order of an element 4 2.2. Equivalence relation, Lagrange's theorem, Cyclic group 9 2.3.
More informationSome practice problems for midterm 2
Some practice problems for midterm 2 Kiumars Kaveh November 14, 2011 Problem: Let Z = {a G ax = xa, x G} be the center of a group G. Prove that Z is a normal subgroup of G. Solution: First we prove Z is
More informationKnow the Wellordering principle: Any set of positive integers which has at least one element contains a smallest element.
The first exam will be on Monday, June 8, 202. The syllabus will be sections. and.2 in Lax, and the number theory handout found on the class web site, plus the handout on the method of successive squaring
More informationNUMBER THEORY. Anwitaman DATTA SCSE, NTU Singapore CX4024. CRYPTOGRAPHY & NETWORK SECURITY 2018, Anwitaman DATTA
NUMBER THEORY Anwitaman DATTA SCSE, NTU Singapore Acknowledgement: The following lecture slides are based on, and uses material from the text book Cryptography and Network Security (various eds) by William
More informationPrime Rational Functions and Integral Polynomials. Jesse Larone, Bachelor of Science. Mathematics and Statistics
Prime Rational Functions and Integral Polynomials Jesse Larone, Bachelor of Science Mathematics and Statistics Submitted in partial fulfillment of the requirements for the degree of Master of Science Faculty
More informationRings and Fields Theorems
Rings and Fields Theorems Rajesh Kumar PMATH 334 Intro to Rings and Fields Fall 2009 October 25, 2009 12 Rings and Fields 12.1 Definition Groups and Abelian Groups Let R be a nonempty set. Let + and (multiplication)
More information2) e = e G G such that if a G 0 =0 G G such that if a G e a = a e = a. 0 +a = a+0 = a.
Chapter 2 Groups Groups are the central objects of algebra. In later chapters we will define rings and modules and see that they are special cases of groups. Also ring homomorphisms and module homomorphisms
More informationMath 511, Algebraic Systems, Fall 2017 July 20, 2017 Edition. Todd Cochrane
Math 511, Algebraic Systems, Fall 2017 July 20, 2017 Edition Todd Cochrane Department of Mathematics Kansas State University Contents Notation v Chapter 0. Axioms for the set of Integers Z. 1 Chapter 1.
More informationA Generalization of Wilson s Theorem
A Generalization of Wilson s Theorem R. Andrew Ohana June 3, 2009 Contents 1 Introduction 2 2 Background Algebra 2 2.1 Groups................................. 2 2.2 Rings.................................
More informationAN ALGEBRA PRIMER WITH A VIEW TOWARD CURVES OVER FINITE FIELDS
AN ALGEBRA PRIMER WITH A VIEW TOWARD CURVES OVER FINITE FIELDS The integers are the set 1. Groups, Rings, and Fields: Basic Examples Z := {..., 3, 2, 1, 0, 1, 2, 3,...}, and we can add, subtract, and multiply
More informationa the relation arb is defined if and only if = 2 k, k
DISCRETE MATHEMATICS Past Paper Questions in Number Theory 1. Prove that 3k + 2 and 5k + 3, k are relatively prime. (Total 6 marks) 2. (a) Given that the integers m and n are such that 3 (m 2 + n 2 ),
More informationMathematical Olympiad Training Polynomials
Mathematical Olympiad Training Polynomials Definition A polynomial over a ring R(Z, Q, R, C) in x is an expression of the form p(x) = a n x n + a n 1 x n 1 + + a 1 x + a 0, a i R, for 0 i n. If a n 0,
More informationMATH 25 CLASS 21 NOTES, NOV Contents. 2. Subgroups 2 3. Isomorphisms 4
MATH 25 CLASS 21 NOTES, NOV 7 2011 Contents 1. Groups: definition 1 2. Subgroups 2 3. Isomorphisms 4 1. Groups: definition Even though we have been learning number theory without using any other parts
More informationSection VI.33. Finite Fields
VI.33 Finite Fields 1 Section VI.33. Finite Fields Note. In this section, finite fields are completely classified. For every prime p and n N, there is exactly one (up to isomorphism) field of order p n,
More informationFactorization in Integral Domains II
Factorization in Integral Domains II 1 Statement of the main theorem Throughout these notes, unless otherwise specified, R is a UFD with field of quotients F. The main examples will be R = Z, F = Q, and
More information