Cryptography — Mathematics 1580
Detailed Syllabus and Homework Assignments
Brown University — Fall, 2017
Professor Joe Silverman
Return to the Math 158 Home Page
Class # | Date | Topic | Read | HW Assignment | HW Due |
---|---|---|---|---|---|
1 | Weds, Sept 06, 2017 | Introduction to cryptology | § 1.1 (not § 1.1.1) | # 1.2(b), 1.3, 1.5(a) | Mon Sept 11 |
2 | Fri, Sept 08, 2017 | Divisibility and gcd | § 1.2 | # 1.6(c), 1.7(b), 1.8(b), 1.9(b,c), 1.10(c), 1.13 | Mon Sept 11 |
3 | Mon, Sept 11, 2017 | Modular arithmetic | § 1.3 | # 1.15(a,c), 1.16(b,e), 1.17(b,c), 1.18, 1.21(a), 1.23(a) | Mon Sept 18 |
4 | Weds, Sept 13, 2017 | Primes, finite fields, primitive roots | § 1.4, 1.5 | # 1.26, 1.28, 1.29, 1.30(a), 1.32(a) | Mon Sept 18 |
5 | Fri, Sept 15, 2017 | Brief history of cryptology Symmetric and asymmetric ciphers |
§ 1.6, 1.7 | # 1.39, 1.40, 1.43, 1.45, 1.46 | Mon Sept 18 |
6 | Mon, Sept 18, 2017 | Birth of public key crypto Discrete logarithm problem (DLP) Diffie-Hellman key exchange |
§ 2.1, 2.2, 2.3 | # 2.3, 2.4(a,c), 2.6, 2.7(a) | Mon Sept 25 |
7 | Weds, Sept 20, 2017 | Diffie-Hellman key exchange Elgamal public key cryptosystem |
§ 2.3, 2.4 | # 2.8, 2.9, 2.10 | Mon Sept 25 |
8 | Fri, Sept 22, 2017 | Groups / Difficulty of DLP | § 2.5, 2.6 | # 2.11, 2.12, 2.13, 2.14(a,c), 2.16(b,c,f) | Mon Sept 25 |
9 | Mon, Sept 25, 2017 | DLP collision algorithm Chinese remainder theorem |
§ 2.7, 2.8 | # 2.17(a), 2.18(a,b) | Weds Oct 4 |
10 | Weds, Sept 27, 2017 | Euler's formula | § 3.1 | # 3.1(b,c), 3.3, 3.4(a,b) | Weds Oct 4 |
11 | Fri, Sept 29, 2017 | RSA public key cryptosystem | § 3.2, 3.3 | # 3.6, 3.8(b), 3.9(a,b), 3.11(b) | Weds Oct 4 |
12 | Mon, Oct 02, 2017 | Exam #1 — Chapters 1 & 2 | — | ||
13 | Weds, Oct 04, 2017 | Primality testing | § 3.4 | # 3.13(a,b-ii,c,d), 3.14(b,c), 3.18 |
Weds Oct 11 |
14 | Fri, Oct 06, 2017 | Pollard p-1 method
Factorization via x^{2} - y^{2} |
§ 3.5, 3.6 | # 3.21(a,b), 3.22(a,c,d,e,f), 3.23(a,b) | Weds Oct 11 |
— | Mon, Oct 09, 2017 | No class - Brown holiday | — | ||
15 | Weds, Oct 11, 2017 | Factorization via x^{2} - y^{2}
Smooth numbers |
§ 3.6, 3.7 | # 3.24(b), 3.25(a,b), 3.26(a,b), 3.27(a,b,c) | Mon Oct 16 |
16 | Fri, Oct 13, 2017 | Smooth numbers and sieves | § 3.7 | # 3.28, 3.29 | Mon Oct 16 |
17 | Mon, Oct 16, 2017 | Sieves | § 3.7 | # 3.33 | Mon Oct 23 |
18 | Weds, Oct 18, 2017 | Index calculus and DLP | § 3.8 | # 3.35 | Mon Oct 23 |
19 | Fri, Oct 20, 2017 | Digital signatures — RSA | § 4.1, 4.2 | # 4.1, 4.2, 4.3 | Mon, Oct 23 |
20 | Mon, Oct 23, 2017 | Digital signatures — Elgamal & DSA | § 4.3 | # 4.4, 4.5, 4.6, 4.7 | Mon Oct 30 |
21 | Weds, Oct 25, 2017 | Elliptic curves | § 6.1 | # 6.1, 6.2, 6.4 | Mon Oct 30 |
22 | Fri, Oct 27, 2017 | Elliptic curves over finite fields | § 6.2 | # 6.5(a,b), 6.6(b), 6.7(c,d) | Mon Oct 30 |
23 | Mon, Oct 30, 2017 | Elliptic curve discrete log problem and elliptic curve cryptography |
§ 6.3, 6.4 | # 6.8, 6.9, 6.10(a), 6.11(a,b), 6.13(a,b), 6.15 | Mon Nov 6 |
24 | Weds, Nov 01, 2017 | Exam #2: Chapter 3, Sections 3.1–3.8 Chapter 4, Sections 4.1–4.3 |
— | ||
25 | Fri, Nov 03, 2017 | Lenstra's elliptic curve factorization algorithm |
§ 6.6 | # 6.18(a,b) | Mon Nov 6 |
26 | Mon, Nov 6, 2017 | Lattice-Based Cryptography | § 7.3–7.4 | # TBA | Mon Nov 13 |
27 | Weds, Nov 8, 2017 | Lattice-Based Cryptography | § 7.5–7.6 | # TBA | Mon Nov 13 |
28 | Fri, Nov 10, 2017 | Lattice-Based Cryptography | § 7.7–7.8 | # TBA | Mon Nov 13 |
29 | Mon, Nov 13, 2017 | Lattice-Based Cryptography | § 7.9–7.10 | # TBA | Mon Nov 20 |
30 | Weds, Nov 15, 2017 | Lattice-Based Cryptography | § 7.10–7.11 | # TBA | Mon Nov 20 |
31 | Fri, Nov 17, 2017 | Lattice-Based Cryptography | § 7.12–7.8 | # TBA | Mon Nov 20 |
32 | Mon, Nov 20, 2017 | Lattice-Based Cryptography | § 7.13–7.14 | # TBA | Mon Nov 27 |
Weds, Nov 22, 2017 | Special topic: TBA | — | |||
Fri, Nov 24, 2017 | No class — Thanksgiving | — | |||
33 | Mon, Nov 27, 2017 | Combinatorics | § 5.1 | # 5.2, 5.3, 5.4(acb), 5.6(a,c), 5.7, 5.8 | Mon Dec 4 |
34 | Weds, Nov 29, 2017 | Probability theory I | § 5.3 | # 5.20(a,b,c), 5.21(a,b,c), 5.22, 5.23(a,b), 5.24, 5.25 | Mon Dec 4 |
35 | Fri, Dec 01, 2017 | Probability theory II | § 5.3 | # 5.27, 5.29, 5.30, 5.32(a,b) | Mon Dec 4 |
36 | Mon, Dec 04, 2017 | Collision algorithms | § 5.4 | # 5.34, 5.35, 5.36(a), 5.37 | Mon Dec 11 |
27 | Weds, Dec 06, 2017 | Pollard rho method | § 5.5 | # 5.38, 5.39 | Mon Dec 11 |
38 | Fri, Dec 8, 2017 | Information theory I | § 5.6 | # 5.42, 5.43, 5.44 | Mon Dec 11 |
39 | Weds, Dec 11, 2017 | Information theory II | § 5.6 | # 5.48, 5.49, 5.51(a), 5.53 | Will not be collected. Do this HW and check against the posted solutions. |
Tues, Dec 19, 2017 | Final Exam | Location TBA — 9:00–12:00am |
Return to the Math 158 Home Page