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.16(a,c), 1.17(b,e), 1.18(b,c), 1.19, 1.22(a), 1.24(a) | Mon Sept 18 |
4 | Weds, Sept 13, 2017 | Primes, finite fields, primitive roots | § 1.4, 1.5 | # 1.25, 1.26, 1.31, 1.32(a), 1.34(a) | Mon Sept 18 |
5 | Fri, Sept 15, 2017 | Brief history of cryptology Symmetric and asymmetric ciphers |
§ 1.6, 1.7 | # 1.41, 1.42, 1.45, 1.47, 1.48 | 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.4, 3.5(a,b) | Weds Oct 4 |
11 | Fri, Sept 29, 2017 | RSA public key cryptosystem | § 3.2, 3.3 | # 3.7, 3.9(b), 3.10(a,b), 3.12(b) | Weds Oct 4 |
12 | Mon, Oct 02, 2017 | Exam #1 — Chapters 1 & 2 | — | ||
13 | Weds, Oct 04, 2017 | Primality testing | § 3.4 | # 3.14(a,b-ii,c,d), 3.15(b,c), 3.19 |
Weds Oct 11 |
14 | Fri, Oct 06, 2017 | Pollard p-1 method
Factorization via x^{2} - y^{2} |
§ 3.5, 3.6 | # 3.22(a,b), 3.23(a,c,d,e,f), 3.24(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.25(b), 3.26(a,b), 3.27(a,b), 3.28(a,b,c) | Mon Oct 16 |
16 | Fri, Oct 13, 2017 | Smooth numbers and sieves | § 3.7 | # 3.29, 3.30 | Mon Oct 16 |
17 | Mon, Oct 16, 2017 | Sieves | § 3.7 | # 3.34 | Mon Oct 23 |
18 | Weds, Oct 18, 2017 | Index calculus and DLP | § 3.8 | # 3.36 | 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 | No class - will be made up during reading period |
— | ||
23 | Mon, Oct 30, 2017 | Elliptic curves over finite fields | § 6.2 | # 6.5(a,b), 6.6(b), 6.7(c,d) | 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 | Elliptic curve discrete log problem and elliptic curve cryptography |
§ 6.3, 6.4 | # 6.8, 6.9, 6.11(a), 6.14(a,b), 6.16 | Mon Nov 6 |
26 | Mon, Nov 6, 2017 | Lenstra's elliptic curve factorization algorithm |
§ 6.6 | # 6.19, 6.21(a,b) | Mon Nov 13 |
27 | Weds, Nov 8, 2017 | Pairings and applications: A brief introduction |
§ 6.8–6.10 (bits and pieces) |
— | Mon Nov 13 |
28 | Fri, Nov 10, 2017 | Lattice-Based Cryptography | § 7.3–7.4 | # 7.5, 7.6(a), 7.7, 7.11(a,b,c), 7.12 | Mon Nov 13 |
29 | Mon, Nov 13, 2017 | Lattice-Based Cryptography | § 7.5–7.6 | # 7.13, 7.15, 7.16, 7.17 (7.15 is challenging, do the best that you can.) |
Mon Nov 20 |
30 | Weds, Nov 15, 2017 | Lattice-Based Cryptography | § 7.7–7.8 | # 7.18, 7.19, 7.20 (7.19 probably needs a computer algebra system) |
Mon Nov 20 |
31 | Fri, Nov 17, 2017 | Lattice-Based Cryptography | § 7.9–7.10 | 7.22(a,b), 7.23(a,b), 7.25, 7.29, 7.32 | Mon Nov 27 |
32 | Mon, Nov 20, 2017 | Lattice-Based Cryptography | § 7.10–7.11 | # 7.36, 7.37 | Mon Nov 27 |
Weds, Nov 22, 2017 | Special topic: Elliptic Curves | — | |||
Fri, Nov 24, 2017 | No class — Thanksgiving | — | |||
33 | Mon, Nov 27, 2017 | Lattice-Based Cryptography | § 7.12 | # 7.39, 7.40 | Mon Dec 4 |
34 | Weds, Nov 29, 2017 | Lattice-Based Cryptography | § 7.13–7.14 | # 7.45(a), 7.47, 7.48 (Bonus for programmers: 7.49) |
Mon Dec 4 |
35 | Fri, Dec 01, 2017 | Combinatorics | § 5.1 | # 5.2, 5.3, 5.4(a,b,c), 5.6(a,c), 5.7, 5.8 | Mon Dec 4 |
36 | Mon, Dec 04, 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 11 |
27 | Weds, Dec 06, 2017 | Probability theory II | § 5.3 | # 5.28, 5.30, 5.32, 5.34(a,b) | Mon Dec 11 |
38 | Fri, Dec 8, 2017 | Collision algorithms | § 5.4 | # 5.36, 5.37, 5.38(a), 5.39 | Mon Dec 11
Click here for solutions. |
39 | Mon, Dec 11, 2017 | Pollard rho method | § 5.5 | # 5.40, 5.41 | Will not be collected. Do this HW and click here to check against the posted solutions. |
Tues, Dec 19, 2017 | Final Exam | Kassar House – Foxboro Auditorium 9:00–12:00am |
Return to the Math 158 Home Page