Cryptography — Mathematics 1580
Detailed Syllabus and Homework Assignments
Brown University — Fall, 2017
Professor Joe Silverman

Return to the Math 158 Home Page


Homework Assignments for Math 1580 *** Tentative ***


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 x2 - y2
§ 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 x2 - y2
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