Topics covered in class:

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.