Fall 2003 Peter Selinger |
1. Sept 5: Introduction and overview; divisibility. Rings, look at Z_5, Z_6 examples. Applications: Codes: plain, error-correcting, compression, cryptographic (symmetric, public) Counting (Polya, see sample problem on Course Info Sheet). Handout 1 (what is a proof) Divisibility: definition (p.37) Lemma 1: a|b, b<>0 => |a|%lt;=|b|. Lemma 2: a|b, b|a => a = +-b. (1.2 Thm.2(3)). 2. Sept 9: Ideals of integers Ideals of integers: see handout 2. Homework: Handout 2 #1-4, Textbook #1.2.7, 1.2.16, due 9/16. 3. Sept 12: lcm, gcd, relatively prime, d=an+bm theorem, division with remainder 4. Sept 16: Euclidean algorithm, primes, unique factorization, ring preview. Euclidean algorithm: p.39. Find d=gcd(m,n), and solve an+bm=d by bottom-up substitution method. Lemma (p.38, Ex. 3): if m=qn+r, gcd(m,n)=gcd(n,r). Primes: (1) p>=2, (2) if d|p and d>0, then d=1 or d=p. LEMMA: (Thm 5, p.41): m,n relatively prime. (1) if m|k, n|k, then mn|k (lcm(m,n)=mn) (2) If m|kn for some k, then m|k. Thm 6 (p.41) Euclid's Lemma: Let p a prime. (1) if p|mn then p|m or p|n, (2) if p|m_1m_2...m_r => ... Thm 7 (p.42) Prime factorization (unique factorization): (1) Every integer n>=2 is a product of (>=1) primes (2) The factorization is unique up to the order of the factors. 5. Sept 19: integers mod n, solving equation mod n Section 1.3 until Example 11. Homework: 1.2 #17-19,24,25; 1.3 #19,27; 3.1 #4,10,18, due 9/30. 6. Sept 23: (commutative) rings. (Axioms R1-R7 and R8) Examples Z, Q, R, C, Z_n, R[x], R[x,y], M_2(R) (non-commutative), F(X,R), RxS. Basic properties: cancelation, Thm 1+2 p.191f. Characteristic of a ring R: smallest n such that 1+1+...+1=0 (n times), or 0 if there is no such n. Lemma: if char R=0, then for all a in R, a+a+...+a=0. 7. Sept 26: Public-key cryptography, RSA cryptosystem See Handout 3. 8. Sept 30: Chinese Remainder Theorem, square roots of unity See Handout 3. Homework: Problem Set 3, due 10/10. 9. Oct 3: Security of the RSA cryptosystem See Handout 3. 10. Oct 7: Fermat and strong pseudoprimes, primality testing See Handout 4. 11. Oct 10: Zero divisors, integral domains, fields, field of fractions 12. Oct 14: Linear algebra mod p, Echelon form, error-correcting codes. Alphabet, (n,k)-codes, expansion ratio=n/k, information rate=k/n. Channel: error rate, error model: independent or in bursts. Goals: * keep information rate high * maximize error correction capabilities * efficient and simple encoding/decoding Parity code (add one parity bit: detects single bit-error) ISBN code (alphabet={0,1,...,9,X}, a10 = 1*a1+2*a2+...+9*a9 (mod 11)) ISBN code detects single digit error, or the swapping of any two digits. 13. Oct 21: Linear codes. See Section 2.11. A code as a subset of Z_p^n. Linear code = subspace. Generator matrix. Nearest neighbor decoding. Hamming weight, Hamming distance. 14. Oct 24: Hamming codes Coset decoding: standard array for C, coset leader. Parity check matrix, syndrome decoding. Hamming codes. 15. Oct 28: Midterm 16. Oct 31: systematic linear codes, polynomial and Euclidean rings Systematic code: generator matrix of the form G=(I|A), parity check matrix of the form H=(-A^t|I)^t. Polynomials, constant polynomials, monic polynomials, degree. Division algorithm for polynomials f(x)=g(x)q(x)+r(x) where d(r(x))%lt;d(g(x)). Remainder Theorem, Factor Theorem, Root Theorem. Euclidean rings. Examples: Z, k[x], Z[i]. Proof that Z[i] is a Euclidean ring. Greatest common divisors in Euclidean rings (they exist and g=sa+tb). Euclidean algorithm in Euclidean rings. Example: find a gcd of x^3+x^2+2x+2 and x^4+3x^3+3x^2+6x+2. 17. Nov 4: reducible and irreducible elements in Euclidean rings, unique factorization in Euclidean rings. Note: each element of a Euclidean ring is exactly one of the following: (a) zero, (b) a unit, (c) reducible, (d) irreducible. In particular, "irreducible" is not the same as "not reducible" - because the terms "reducible" and "irreducible" are only applied to non-zero non-units. 18. Nov 7: irreducible polynomials in C, R, Q, Z, and Z_p. Rational roots theorem, Gauss's Lemma. 19. Nov 11: Eisenstein's criterion, polynomial codes. Lemma: if p(x) is a polynomial over Z_2, then p(x^2)=p(x)^2. Thus, if x is a root of p(x), then so is x^2. 20. Nov 14: ideals, principal ideal rings, quotients R/I, quotients k[x]/(p(x)) 21. Nov 18: when is k[x]/(p(x)) a field? Finite fields, order of elements, primitive elements. Theorem without proof: for every prime p and every m>0, there exists a finite field of size p^m. Theorem without proof: any two finite fields of the same size are isomorhic. Theorem: Every finite field has size p^m, where p is prime and m>0. The unique field with p^m is called the Galois Field of order p^m and is denoted GF(p^m). Examples: GF(4) = Z_2[x]/(x^2+x+1) GF(8) = Z_2[x]/(x^3+x+1) GF(9) = Z_3[x]/(x^2+1) GF(27) = Z_3[x]/(x^3+2x+1) GF(16): see handout 5. Theorem without proof: every finite field of size n has a primitive element, i.e., an element of order n-1. 22. Nov 21: Vandermonde determinant. Irreducible polynomial with a given element as a root. BCH codes. Vandermonde determinant: let x_1,...,x_n be elements in a field, and let A be the nxn-matrix with entries a_ij = (x_i)^j. Then det A = product_(i<j) (x_j-x_i). In particular, if all x_i are distinct, this determinant is non-zero. If k is a subfield of k', then k' is also called a field extension of k. Theorem: If k' is a field extension of k, and if a is an element of k', then there exists a unique monic irreducible polynomial p(x) in k[x] with p(a)=0. BCH codes (1960 Bose, Chaudhari, Hocquenghem). "The most powerful class of error-correcting codes" Theorem: For any positive integers m,t with t<2^(m-1), there exists a BCH code of length n=(2^m)-1 that will correct any combination of t or fewer errors. It is a polynomial code with generator of degree <= mt, thus, the plaintext length is k >= n-mt. Examples: m n t k 2 3 1 1 (3,1)-code, 1-error correcting [repeat everything 3x] 3 7 1 4 (7,4)-code, 1-error correcting [equiv. Hamming code] 3 7 2 1 (7,1)-code, 2-error correcting [repeats everything 7x] 4 15 1 11 (15,11)-code, 1-error correcting [equiv. Hamming code] 4 15 2 7 (15,7)-code, 2-error correcting 4 15 3 3 (15,3)-code, 3-error correcting 8 255 1 247 (255,247)-code, 1-error correcting [equiv. Hamming code] 8 255 2 239 (255,239)-code, 2-error correcting 8 255 8 191 (255,191)-code, 8-error correcting 8 255 31 7 (255,7)-code, 31-error correcting Definition. A t-error correcting BCH code of length n=(2^m)-1 is constructed as follows. Let a be a primitive element in GF(2^m). Let p_i(x) in Z_2[x] be the irreducible polynomial with a^i as a root. Then let p(x)=LCM(p_1(x),...,p_2t(x)). The code has p(x) as generator polynomial. Example: to construct the 2-error correcting (15,7)-code, we set t=2, m=4 (thus n=15). Let a be a primitive element in GF(16) (see handout 5). The irreducible polynomial with a as a root is p_1(x)=x^4+x+1. Then a^2 and a^4 are also roots of p_1(x), thus p_1(x)=p_2(x)=p_4(x). The irreducible polynomial with a^3 as a root is p_3(x)=x^4+x^3+x^2+x+1. Thus, the generator polynomial for this code is p(x) = LCM(p_1(x),...,p_4(x)) = p_1(x) p_3(x) = (x^4+x+1)(x^4+x^3+x^2+x+1) = x^8+x^7+x^6+x^4+1. 23. Nov 25: Error correction capabilities of BCH codes. Compression and Huffman codes. 24. Nov 28: Huffman codes, the BZIP algorithm.