Math 3343, Applied AlgebraFall 2003 Peter Selinger

### 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.

```

Back to 3343 Homepage.
Peter Selinger / Department of Mathematics and Statistics / Dalhousie University
selinger@mathstat.dal.ca / PGP key