교재준비작업(1)
2004.10.03 21:27
이산수학과 유한체이론 - 주별 강의주제 목록
1. Property of Z
Z is a commutative ring with 1.
it is an integral domain.
it is a Euclidean domain.
it is a Unique Factorization domain.
Z/(n) is a ring, domain, ED, and UFD.
G=U(Z/(n)) is a multiplicative group of order phi(n)
it is cyclic if and only if n=1,2,4,p^k, 2p^k.
Z/(n) is a field if and only if n=prime
U(Z/(p)) is cyclic of order p-1
2. Computations over Z
Linear equation over Z/(n)
Chinese Remainer Theorem
Quadratic equation over Z/(n)
Quadratic Reciprocity Theorem - Legendre/Jacobi symbols
Payley construction of Hadamard matrix
Big Integer arithematic
Fast Exponentiation
3. Some Public Key Crypto Algorithms
Primality testing algorithm
DLP - analysis
ElGamal Algorithm
RSA Algorithm
Secrete Sharing Algorithm
Coin-flipping over Telephone
Public key Envelope
4. Permutations and Counting
Definition, notation, order, cycles
unique decomposition
even and odd permutation
Not-Burnside Theorem on counting
5. Vectors and Matrix
n-tuple vector space over F
Basis, Linear Independance
simultaneous equation and coefficient matrix
Gauss Elimination, rank of a matrix, LU decomposition
column space, row space, orthogonal complement
rank, nullity, basic relation
Vandemond matrix
6. Linear Transformation and Matrix
Definition of Linear Transformation
Range space and Null space, basic relation
relation to Matrix
Multi-linear transformation and Determinant
Existence of Determinant
7. Some Problem Discussions
8. midterm
9. Polynomial over GF(p) = Fp[x]
Fp[x] is a commutative ring with 1.
it is an integral domain.
it is a Euclidean domain.
it is a Unique Factorization domain.
Fp[x]/(f(x)) is a ring, domain, ED, and UFD.
Fp[x]/(f(x)) is a field if and only if f(x) is irreducible
10. Structure of Finite Field
Extension and Subfield
Additive structure
Multiplicative structure and conjugate class
Addone table
Homomorphism and isomorphism
11. Irreducible Polynomial over finite field
irreducible polynomials over F2
Property of minimal polynomials
Conjugates
Trace function
m-sequence
12. Irreducible Polynomial and Cyclotomic Polynomial
x^{q^n}-x = ㅠ V_d(x)
Number of irreducible polynomials
Cyclotomic Polynomials
over C
over Finite Field
Some Factoring
13. Error-correcting linear codes
binary symmetric channel, binary erasure channel
binary linear code and minimum distance decoding
Binary Hamming code and decoding
minimum distance decoding is ML decoding
BCH code over Z/(p)
Some nonlinear simultaneous equations for decoding of BCH code over Z/(p)
14. Cyclic code
Hamming code and BCH code as cyclic code
RS codes - encoding and decoding
GFFT approach
15. Some Problem Discussions
16. final exam
1. Property of Z
Z is a commutative ring with 1.
it is an integral domain.
it is a Euclidean domain.
it is a Unique Factorization domain.
Z/(n) is a ring, domain, ED, and UFD.
G=U(Z/(n)) is a multiplicative group of order phi(n)
it is cyclic if and only if n=1,2,4,p^k, 2p^k.
Z/(n) is a field if and only if n=prime
U(Z/(p)) is cyclic of order p-1
2. Computations over Z
Linear equation over Z/(n)
Chinese Remainer Theorem
Quadratic equation over Z/(n)
Quadratic Reciprocity Theorem - Legendre/Jacobi symbols
Payley construction of Hadamard matrix
Big Integer arithematic
Fast Exponentiation
3. Some Public Key Crypto Algorithms
Primality testing algorithm
DLP - analysis
ElGamal Algorithm
RSA Algorithm
Secrete Sharing Algorithm
Coin-flipping over Telephone
Public key Envelope
4. Permutations and Counting
Definition, notation, order, cycles
unique decomposition
even and odd permutation
Not-Burnside Theorem on counting
5. Vectors and Matrix
n-tuple vector space over F
Basis, Linear Independance
simultaneous equation and coefficient matrix
Gauss Elimination, rank of a matrix, LU decomposition
column space, row space, orthogonal complement
rank, nullity, basic relation
Vandemond matrix
6. Linear Transformation and Matrix
Definition of Linear Transformation
Range space and Null space, basic relation
relation to Matrix
Multi-linear transformation and Determinant
Existence of Determinant
7. Some Problem Discussions
8. midterm
9. Polynomial over GF(p) = Fp[x]
Fp[x] is a commutative ring with 1.
it is an integral domain.
it is a Euclidean domain.
it is a Unique Factorization domain.
Fp[x]/(f(x)) is a ring, domain, ED, and UFD.
Fp[x]/(f(x)) is a field if and only if f(x) is irreducible
10. Structure of Finite Field
Extension and Subfield
Additive structure
Multiplicative structure and conjugate class
Addone table
Homomorphism and isomorphism
11. Irreducible Polynomial over finite field
irreducible polynomials over F2
Property of minimal polynomials
Conjugates
Trace function
m-sequence
12. Irreducible Polynomial and Cyclotomic Polynomial
x^{q^n}-x = ㅠ V_d(x)
Number of irreducible polynomials
Cyclotomic Polynomials
over C
over Finite Field
Some Factoring
13. Error-correcting linear codes
binary symmetric channel, binary erasure channel
binary linear code and minimum distance decoding
Binary Hamming code and decoding
minimum distance decoding is ML decoding
BCH code over Z/(p)
Some nonlinear simultaneous equations for decoding of BCH code over Z/(p)
14. Cyclic code
Hamming code and BCH code as cyclic code
RS codes - encoding and decoding
GFFT approach
15. Some Problem Discussions
16. final exam
