- 상대평가: A=45%, B=50%, 나머지=5%.
- 학부생과 대학원생은 분리평가.
- 학부생이 10명 미만인 경우 절대평가 실시함.
기타사항:
- 무단결석 3회=F학점
- HW제출기한= 다음 주 첫 수업시간 시작시 (시작 후 혹은 수업끝나고나서 받지 않음)
Weekly Plan: (updated after midterm exam)
|
Objective |
▶ Elementary Number Theory ▶ Important Concepts in Modern Algebra ▶ Finite Fields ▶ BCH and RS Codes, RSA/ElGamal Cryptography | ||
|
Week |
Summary |
Remark |
Homework |
|
1 |
Integers and Congruence |
|
HW#1 |
|
2 |
(응용) RSA/ElGamal Encryption Algorithms |
|
Project #1 |
|
3 |
Groups and Permutations |
|
HW#2 |
|
4 |
Theory of Counting - Burnside Lemma |
|
HW#3 |
|
5 |
Simultaneous Equations and Vector Spaces |
|
HW#4 |
|
6 |
Matrix/Determinants/Linear Transformations |
|
HW#5 |
|
7 |
Review of the first half semester |
|
|
|
8 |
Midterm Exam |
|
|
|
9 |
Some Concepts in Modern Algebra |
|
HW#6 |
|
10 |
Irreducible Polynomials over Fp |
|
HW#7 |
|
11 |
Multiplicative Structure of Finite Fields |
|
HW#8 |
|
12 |
Additive Structure of Finte Fields |
|
HW#9 |
|
13 |
(응용) Hamming/BCH Codes - Encoding/Decoding |
|
Project #2 |
|
14 |
(응용) Reed-Solomon Codes - Encoding/Decoding |
|
HW#10 |
|
15 |
Review of the second half semester |
|
|
|
16 |
Final Exam (12주-15주 수업내용) |
|
|
Weekly Plan:
Objective | ▶ Elementary Number Theory ▶ Important Concepts in Modern Algebra ▶ Finite Fields ▶ BCH and RS Codes, RSA/ElGamal Cryptography | ||
Week | Summary | Remark | Homework |
1 | Integers and Congruence |
| HW#1 |
2 | (응용) RSA/ElGamal Encryption Algorithms |
| Project #1 |
3 | Groups and Permutations |
| HW#2 |
4 | (응용) Burnside and Polya Theory of Counting |
| HW#3 |
5 | Simultaneous Equations and Vector Spaces |
| HW#4 |
6 | Matrix/Determinants/Linear Transformations |
| HW#5 |
7 | Some Concepts in Modern Algebra |
|
|
8 | Midterm Exam (5,6,7주 수업내용) |
|
|
9 | Irreducible Polynomials over Fp |
| HW#6 |
10 | Multiplicative Structure of Finite Fields |
| HW#7 |
11 | Additive Structure of Finte Fields |
| HW#8 |
12 | (응용) Linear Feedback Shift Register Sequences |
| HW#9 |
13 | (응용) Hamming/BCH Codes - Encoding/Decoding |
| Project #2 |
14 | (응용) Reed-Solomon Codes - Encoding/Decoding |
| HW#10 |
15 | (응용) Latin Squares and Finite Projective Planes |
|
|
16 | Final Exam (12주-15주 수업내용) |
|
|
Details
1주 Integers and Congruence
- Congruence mod n
- 1차방정식 mod n
- Chinese Remaindr Theorem
- Fermat's Little Theorem
- Euler's Theorem
- Quadratic Residues mod p
- Quadratic Reciprocity Theorem
- 2차방정식 mod n
- Number theoretic functions/identity
HW#1
2주 (응용) RSA/ElGamal Encryption Algorithms
- Introduction to Public Key Crypto-system
- Probabilistic Primality Testing
- Finding Primitive root mod p -- Gauss Algorithm
- Fast Exponentiation Algorithm
- Introduction to Hash Function
- RSA/ElGamal Encryption Algorithm
- Diffi-Hellman Key Exchange Algorithm
- ElGamal Signature Algorithm
Project #1: Implementation of ElGamal signature algorithm
3주 Groups and Permutations
- Definition
- Subgroup/Normal subgroup
- Cosets/Quotient Group
- Lagrange Theorem
- Order of Element/Group
- Cyclic Group
- Introduction to Permutation Group Sn
- Cycle Structure
- Representation of permutation
- Dihedral Group of Permutations
HW#2
4주 (응용) Burnside and Polya Theory of Counting
- Group Action
- Orbit
- Stabilizer
- Size of Orbit
- Number of Orbits
- Burnside's Lemma on Counting the number of orbits
- Lots of Examples
HW#3
5주 Simultaneous Equations and Vector Spaces
- Homogeneous System of Linear Equations
- Non-homogeneous System of Linear Equations
- Introduction to Vector Spaces over Field
- n-tuple vector space of F_p over F_p
- Subspace
- Basis/Dimension
HW#4
6주 Matrix/Determinants/Linear Transformations
- Linear Transformation on Vector Spaces
- Matrix Representation of Linear Transformation
- Rank of a Matrix
- Determinant of a Matrix as a bi-linear function
- Homomorphism of Vector Spaces
- Isomorphism of Vector Spaces
HW#5
7주 Some Concepts in Modern Algebra
- Polynomial Ring
- Integral Domain
- Euclidean Domain
- Unique Factorization Domain
- Ideal of a Ring/Maximal Ideal/Principal Ideal
- Quotient Ring
- Automorphism Group
- Introduction to Finite Fields
8주 Midterm Exam
9주 Irreducible Polynomials over GF(p)
- Irreducible polynomial over GF(p) and Extension Field
- Finding irreducible polynomials mod p - Sieve method
- Number of irreducible polynomials mod p
- Period of irreducible polynomials mod p
- Rational Cubic Transformation on polynomials over GF(2)
- Primitivity of roots of irreducible polynomials over GF(p)
HW#6
10주 Multiplicative Structure of Finte Fields
- Minimal Polynomial of elements in GF(p^n) over GF(p)
- Properties of minimal polynomial of elements in GF(p^n) over GF(p)
- Cyclotomic Cosets mod p^n -1
- Conjugacy Classes
- Trace Functions and Subfields
HW#7
11주 Additive Structure of Finite Fields
- Additive identity of Finite Field
- Charateristic of a Finite Field
- Factoring of
into irreducible factors over GF(p) - Polynomial Basis/Normal Basis
- Representation of Elements of finite fields
- Add-one table
HW#8
12주 (응용) Linear Feedback Shift Register Sequences
- Introduction ot Linear Feedback Shift Register
- Connection polynomial is the characteristic polynomial
- Period of output sequence is the period of connection polynomial
- Generating function approach
- Introduction to m-sequences
- Properties of m-sequences
HW#9
13주 (응용) Hamming/BCH Codes - Encoding/Decoding
- Block Codes as Vector Subspace of the n-tuple space of F_p over F_p
- Hamming Distance and Error Correction/Detection Capability of a block code
- Minimum distance decoding and syndrom decoding
- Definitions of Hamming codes and Extended/Shortened Hamming codes
- Encoding and Decoding of Hamming codes
- Definition of Primitive Irreducible double-error-correcting BCH codes
- Encoding and Decoding of BCH Codes
Project #2: Implementation of BCH Encoder/Decoder
14주 (응용) Reed-Solomon Codes - Encoding/Decoding
- Functions on a finite fields
- Fourier Transform - Definition and Properties
- Original Definition of RS Codes and Error Correction Capability
- RS Codes as Special type of BCH Codes
- Transform Domain encoding and decoding
HW#10
15주 (응용) Latin Squares and Finite Projective Planes
- Definition of Latin Squares
- Mutually orthogonal latin squares
- Finite Projective Plane
- Hyper Oval
16주 Final Exam