Applied Algebra
Course Information
Textbook: Elementary Number Theory; Primes, Congruences, and Secrets by William Stein
Classes: Mon 10:30~11:45 (자2-420호); Thr 13:30~14:45 (수학과전산실)
Grades: 2 Midterms (200 points), Final Exam (100 points), Homework, Quizzes and Projects (200 points)
Instructor's Office Hours: Mon 16~17; Wed 14~15 (Room 417)
Teaching Assistants: Choi, Hwan-Hyuk (최환혁) whchoi@kangwon.ac.kr (Room 415)
Announcement
- 2014년 1월 6일~9일에 서울대학교에서 Joseph Silverman 교수의 강연이 있습니다. 관심있는 학생들은 강연을 들어보기 바랍니다. "Eight Lectures on Elliptic Curves and Lattices"
- 12/19 Final Exam covers Chapters 4, 5 and 6 and labs
- Supplementary lecture schedule: Dec. 10; Dec.12 (Time 1:30~3pm); Dec. 13(3~4:30pm)
- 11/14 Lecture takes place in Room 405 due to entrance exam
- 10/24 Coding with Sage - Test Material PDF - Code examples
- 10/21 Midterm 1 covers Chapters 1, 2 and 3
- 9/26 No Lecture but there will be Sage Help Time
Topics covered in class
- 9/2 Chapter 1 Primes
- 9/5 Introduction to SAGE and performing SAGE problems in Chapter 1 SAGE lab1 -PDF
- 9/9 Proof of Fundamental Theorem of Arithmetic, infinitude of primes, prime sieve algorithm, infinitude of primes of the form 4x-1
- 9/12 Congruences modulo n, quotient ring Z/nZ SAGE lab2 -PDF
- 9/16 Unit group, Euler theorem, Wilson theorem
- 9/23 Extended Euclidean algorithm, Chinese remainder theorem, multiplicativity of Euler function
- 9/30 Algorithms for finding multiplicative inverse of a number modulo n and computing powers modulo n; pseudoprimality test
- 10/7 Miller-Rabin primality test; existence of primitive roots
- 10/10 Number of primitive roots; Diffie-Hellman key exchnage; discrete log problem
- 10/14 RSA cryptosystem
- 10/17 More cryptosystem and SAGE practice
- 10/28 Statement of quadratic reciprocity law; Euler's criterion
- 11/4 Gauss' lemma, a proof of quadratic reciprocity theorem
- 11/11 Euler's theorem for quadratic reciprocity theorem, Gauss sum
- 11/14 Proof of quadratic reciprocity law using Gauss sum; algorithm for finding a square root of a quadratic residue
- 11/18 Finite continued fractions; every rational number is represented by a finite simple continued fraction
- 11/25 Every real number is the value of a simple continued fraction
- 11/28 Every quadratic irrational is the value of a simple periodic continued fraction; every prime congruent to 1 modulo 4 is a sum of two squares
- 12/2 Elliptic curve, group structure on an elliptic curve, B-power smooth, Pollard (p-1)-method
- 12/5 Lenstra's elliptic curve factorization method, elliptic curve analogs of Diffie-Hellman,elliptic curve discrete logarithm problem
- 12/12 Torsion subgroup and rank of elliptic curves over the rational numbers, congruent numbers
Homework Assignments
- Set 1 (due 9/16) Exercises 1.3 except for number 6
- Set 2 (due 9/23) Exercises 2.6 #1,2,7,8,12,18,21,22
- Set 3 (due 9/30) Exercises 2.6 #3,5,13,16,17,19
- Set 4 (due 10/7) Exercises 2.6 #4,10,11,14,15,20,25,26,30; Study Algorithm 2.4.4 and two sage code examples in p.39
- Set 5 (due 10/14) Exercises 2.6 #6,23,24,27,28,31,32,33; Exercises 3.5 #4,5
- Practice with the rest of the problems in Exercises 3.5
- Set 6 (due 11/4) Exercises 4.6 #1,2,3,4,5,7,8,9,10
- Set 7 (due 11/11) Exercises 4.6 #6, study Lemma 4.3.3
- Sets 6 & 7 revisited (due 11/18) retry the problems
- Set 8 (due 11/25) Exercises 5.8 #1,2,4,5
- Set 9 (due 12/2) Exercises 5.8 #3,7,8,9,10,11
- Set 10 (due 12/10) Exercised 6.6 #1,2,3,4,5,7,8,10