수업일지 -- 유한체이론 및 응용, 2001학년도
1학기, 전기전자공학과
여러분이 이 페이지를 읽는
날짜를 기준으로 하여
이전의 기록은 이미 수업시간에
다루었던 내용을 간추린 것이고 이후의 기록은 대략적인 계획입니다.
자주 들러서 예습/복습에
도움이 되기를 바라며, 열심히 공부하기 바랍니다.
담당교수: 송홍엽
FIRST QUARTER
(GO
TO 1st 2nd 3rd 4th quarter; top today bottom )
1주
3월 2일(금3)
개강.
- 수업 계획서
배포, 교재소개, class rule 설명, 출석부확인, 5회 무단결석 = F학점, 사전
통보(이메일, 전화, 쪽지)한 경우는 무단결석 아님.
- quiz and
solution
3월 7일(수23)
- Chapter
1 Prologue
- Field,
infinite, finite
- integers
mod p
- Chapter
2 Euclidean Domains and Euclid's Algorithm (Theorem 2.1)
- Integral
Domain, Euclidean Domain, GCD
- Three examples
of ED: Integers, Polynomials over a field, Gaussian integers
- Theorem
2.1 Over ED, GCD always exists and expressible as a linear combination
2주
3월 9일(금3)
- Problem
2-10: 문제 수정
- Euclid's
Algorithm: Proof and Extended Version, examples
- Chapter
3 Unique Factorization in Euclidean Domains (Theorem 3.6)
- units,
associates, prime, relatively prime
- Five
Lemmas for Theorem 3.6
- HW#1:
Chapter 2: 2,3,4,10,11, and Chapter 3: 2,6,8,9,11
- 박사과정
수강생의 지정 topic 선정: 학기 후반부에 약 3시간씩 발표예정
- Exponential
Sum, Finite Geometry, Coding Theory, all from the book "Intro.
to Finite Fields..." by Lidl and Niederreiter
3월 14일(수23)
- Theorem
3.6
- Chapter
4 Building Fields from Euclidean Domains (Theorem 4.1
and many examples)
- Chapter
4 Problems: 9,10,11 -- to be included in HW#2
- Everything
of Chapter 4 was covered except for one last long example.
3주
3월 16일(금3)
- HW#1
collected
- Last example
of Chapter 4 and a little more.
- Theorem:
Given a size q, there exists one and only one field of size q up to
isomorphism.
- Some
concept from Linear Algebra
- def
of group, field, vector space, subspace
- number
of k-dim subspaces of Vn over F2
- sum
and product of subspaces
3월 21일(수23)
- Some
concept from Linear Algebra
- Linear
Transformation, null space, range space, some examples
- homomorphism,
isomorphism, and automorphism
- some
results of group theory
- subgroup,
index, cosets, etc
- Chapter
5 begins
- Theorem
5.1: a FF with size q -> q=p^m
for some prime p and integer m>0.
- Theorem
5.2: a=nonzero element of FF of size q ->
ord(a) divides q-1.
4주
3월 23일(금3)
- Chapter
5 continues. Let F be a finite field of size q.
- Lemma
5.3: if p(x) over F is of degree m, then p(x)=0 has at most m roots
over F.
- Lemma
5.4: if alpha in F has order n, then the order of alpha to the s
is equal to n divided by gcd(s,n).
- Theorem
5.5: if t is a positive integer, then F contains either no elements
of order t or exactly phi(t) elements of order t.
- Theorem
5.6: summation of phi(d) over all divisors d of n is equal to n.
(proof: self-exercise)
- Theorem
5.7: if t divides q-1 then F contains exactly phi(t) elements of
order t.
3월 28일(수23)
- HW#2
(10 문항) due: Chapter
5가 끝나는 시간의 다음 수업시간 시작시.
- Chapter 4: 9, 10, 11
- Extra Proof that dimension of V is equal to nullity
and rank of a linear transformation T from V.
- Chapter 5: 3, 4, 6, 7, 8, 14
- Chapter
5 continues.
- Gauss
Algorithm of finding a primitive elements: Big example with F of
size 25.
- Lemma
5.8: if ord(alpha)=m and ord(beta)=n, and (m,n)=1, then ord(alpha
beta)=mn.
- minimal
polynomials: definitions and existence.
- Theorem
5.9: F is a field with size p^m. For each alpha in F, there exists
a unique monic polynomial p(x) in F_p [x] such that (1) p(alpha)=0,
(2) deg(p) <= m, and (3) if f(x) in F_p [x] satisfies f(alpha)=0
then p(x) divides f(x).
- def:
such a polynomial p(x) is called the minimal polynomial of alpha
with respect to F_p.
- NOTE:
minimal polynomial is irreducible.
- when
alpha is a primitive element the p(x) is called primitive polynomial.
SECOND QUARTER (GO TO 1st 2nd 3rd 4th quarter; top today bottom )
5주
3월 30일(금3)
Finish Chapter 5.
We assume
that F is a finite field of size q^n and K is its subfield of size q. We
assume that alpha is an element of F.
- Lemma 5.10:
alpha in F of size q^n is in fact an element of K of size q (K is a
subfield of F) if and only if alpha^q = alpha.
- Lemma 5.11:
p choose k is a multiple of p for k=1,2,...,p-1. p=prime.
- Lemma 5.12:
char(F)=p. then (alpha + beta)^p = alpha^p + beta^p
- def: conjugates
of alpha in F (of size q^n) with respect to K (of size q, and K is a
subfield of F) are alpha, alpha^q, alpha^(q^2), alpha^(q^3),....
- Number
of conjugates of alpha with respect to K is called the degree
of alpha with respect to K.
- Theorem
5.13: the degree d of alpha is a divisor of n. it is the smallest positive
integer such that q^d = 1 (mod ord(alpha)). Furthermore, if a=b (mod
d) then alpha^(q^a)=alpha^(q^b).
- Theorem
5.14: the minimal polynomial of alpha in F with respect to K is given
by (x-alpha)(x-alpha^q)(x-alpha^(q^2))...(x-alpha^(q^(d-1))) where d
is the degree of alpha with respect to K.
- Example
5.8: self-exercise.
- HW#2
- due next Wed.
4월 4일(수23)
Chapter 6 (Existence, Uniqueness, and subfields)
- HW#2 collected
- Review
of materials covered so far
- ch4:
construction of a finite field of size q
- ch5:
abstract properties of a finite field of size q; def and properties
of minimal polynomials
- Existence
& uniqueness & subfields
- Theorem
6.1: x^(q^n) - x is the product of V_d(x) over all the divisors d of
n, where V_d(x) is the product of all the monic irreducible polynomials
of degree d over K of size q.
- Corollary
6.2: q^n = summation of d I_d over all the divisors d of n, where I_d
is the number of monic irreducible polynomials of degree d over K.
- Another
proof of Cor 6.2 --- read, study, and summerize it as an
extra problem #1 of HW#3
- definition
of mu(n) for n=1,2,... called Mobius-mu function
- properties
of mu(n):
- it
is multiplicative, i.e. if (a,b)=1 then mu(ab)=mu(a) mu(b): easy
proof
- for
n>1, the summation of mu(d) over all the divisors d of n becomes
0: proof by induction.
6주
4월 11일(수23)
Chapter 7
- n-th cyclotomic
polynomial over C
- n-th cyclotomic
polynomial over GF(q) of char=p
- theorem
7.1: some relations on cyclotomic polynomials
- theorem
7.2: existence and factoring of n-th cyclotomic polynomial over GF(q)
of char=p
- examples
7주
4월 13일(금3)
Chapter 7
- example
7.4: 180-th cyclotomic polynomial over GF(2)
- factorization
of n-th cyclotomic polynomial over GF(q)
- never
irreducible when n is not of the form 1, 2, 4, p^t, 2p^t.
- when
n is of the form 1, 2, 4, p^t, 2p^t, it is
- irreducible,
if q is primitive root mod n
- not
irreducible, otherwise.
- Berlekamp
algorithm of factoring a polynomial over GF(q)
- Theorem
7.3
- HW#3
Problems (due: 5월 2일 수요일 수업시간)
- Two extra problems in Chapter 6
- Exercise Problems in Chapter 7: 4,5,6,7,8,9,10,11
4월 18일(수23)
Chapter 7
- FINISH:
Berlekamp algorithm of factoring a polynomial over GF(q)
THIRD QUARTER (GO
TO 1st 2nd 3rd 4th quarter; top today bottom )
8주
4월 20일(금3)
Chapter 8
- definition
and properties of trace function from GF(p^t) to GF(p)
9주
5월 2일(수23)
Chapter 8
- calculation
of trace functions
- solvability
of quadratic equations over GF(q)
- HW#4
-- due 5월 23일 (수) 수업시간 시작시
- Chapter 8 Problems: 3, 9, 11, 13, 19 (시험범위에
포함)
- Chapter 9 Problems: 3, 4, 5, 6, 9 (시험범위에
포함 안됨)
10주
5월 4일(금3)
Chapter 8
- dual basis
and bit-serial multiplication over GF(2^m)
- 4세대 이동통신
워크샵 참석차 휴강: 이 부분은 생략합니다.
- Chapter
8의 HW 연습문제 중에서 이 부분은 생략합니다.
5월 9일(수23)
Chapter 9
- Linear
Recurrence
- Properties
of LRS (case: f(x) is irreducible)
11주
5월 11일(금3)
Chapter 9
- Properties
of LRS (case: f(x) is irreducible)
5월
16일(수23) 휴강:국제학술대회 참석 및 논문발표 "Sequences
and Their Applications," Bergen, Norway.
중간시험 (범위: 처음부터
여기까지) up to Chapter 8 (확정)
-- emphasis
on Chapters 5,6,7,8
1. 모든 HW 문제를 복습할 것
2. 위의 모든 Theorem의 증명을 복습할 것 (특히 5장-8장
내에 공부한 모든 Lemma와 Theorem의 증명을 필히 숙지할 것)
3. 그리고도 시간이 있으면 HW에 포함되지 않은 문제를
풀어볼 것.
4. 예상하기로, 문제풀이 5-6개 정도, 증명문제 5-6개
정도. (정확히 2시간)
12주
5월 18일(금3)
휴강:국제학술대회 참석 및 논문발표 "Sequences and Their Applications,"
Bergen, Norway, 5월 12일 - 5월 18일.
5월 23일(수23) 박사과정 발표 1 (신민호: Exponential Sums)
- character
- additive
character of a finite field
- multiplicative
character of a finite field
FOURTH QUARTER (GO
TO 1st 2nd 3rd 4th quarter; top today bottom )
13주
14주
6월 1일(금3)
special topic - cyclic Hadamard difference sets (part I)
6월 2일(토) 보강: 오전10시 - 1시(3시간) B701
Conference on Chapter 10:
박사과정을 제외한 나머지 수강생은 약 10분-15분의
시간동안
할당된 주제의 내용을 정리하여 발표하기 바랍니다.
발표는 10분, 질의응답 5분. Click
this -> "구체적인 내용" for the details.
금일 발표자료를
발표시간 중 이야기 한 모든 내용을 참조하여
수정/보완하여
나에게 다시 email로 보내기 바랍니다.
6월 8일(금)
수업시간 전까지.
이후에 모든
자료를 통합하여 여기에 posting할 계획입니다.
6월 6일(수23)
- 현충일 --- 휴일!
15주
6월 13일(수23) 박사과정 발표 3 (은유창: Bent Function Sequences)
종강일
Class Presentation
평가점수: 구체적인
내용
16주
6월 25일(월) 오전 10시 - 6월 26일(화) 오전 10시
Take-Home
Final
--
come and visit this page for the problem sheets in 25th of June at 10
AM
--
You must submit your answer sheets in A4 size by 10 AM of 26th of June
at my office
--
No delay whatsoever will be accepted.
--
교재 전체에서(6월 8일 수업까지).... 주로 문제풀기 위주임
--
HW문제를 다시 복습하고 중간시험 준비시 공부한 내용을 복습할 것
--
중간시험 이후 수업시간에 다룬 내용에 대해서 복습할 것
- Chapter 10: Linear Feedback Shift Register Sequences
- characters of finite fields
- finite projective plane
- cyclic hadamard difference sets
Final exam download
(답안지 제출: 6월 26일 오전 10:00 까지)
If you have a trouble to access the file, call me at x4861
now.
최종성적처리 완료
2001년 6월 29일.
Go
Back Home
(GO TO 1st 2nd 3rd 4th quarter; top today bottom )
