## Mathematics 3809A Introduction to Number Theory and Cryptgraphy

 Course Outline Topics covered in the class Sep 8: Introduction & Divisibility. Sep 13, 15: Primes and Unique factorization Sep 20, 22: Elementory factoring methods; GCD and LCM. Sep 27, 29: Linear Diophantine equations, Congruence Oct 4, 6: Inverses mod p; Chinese remainder Theorem; Fermat's Theorem. Oct 11, 13: Euler totient function and Euler's Theorem; Lagrange Theorem Midterm covers all the material up to here. Oct 18, 20: Classical cryptography, public key cryptography, The RSA scheme. Oct 25, 27: Probablistic fatoring related to RSA, midterm. Nov 1, 3: Probablistic fatoring related to RSA, probabilistic primality testing, a-pseudoprimes. Nov 8, 10: Pollard's p-1 method, Pollard's \rho method. Nov 15, 17: order, primitive root theorem. Nov 22, 24: Discrete Logarithm, primality testing, ElGamal system.

Tutorials

Tut #1:

• 2.1: 2, 5, 6
• 2.2: 5, 6
• 2.3: 3, 6, 10, 12

Tut #2:

• 2.4: 6, 8
• 2.5: 1(a)(b), 2 (a)(b), 3, 4, 9

Tut #3:

• 2.6: 1 (a) (b), 8
• 3.1: 2 (a) (b), 5, 7, 12, 14.

Tut #4:

• 3.2: 2, 4(a)(b)
• 3.3: 1 (a)(b), 2 (a)(b)

Tut #5:

• 4.1: 1 (a)(b), 3, 9
• 4.2: 1, 4
• 4.3: 1 (a)(c), 3

Tut #6:

• 4.4: 2, and questions from Tut #5

Tut #7:

• 5.1: 1
• 5.2: 1, 2
• 5.3: 2
• Study your notes.

Tut #8:

• Study Example 5.3.6 on page 141 in the textbook.
• 6.1: 1, 2, 9.

Tut #9:

• 6.1: 5
• 6.3: Use Pollard's (p-1) method to factor 341.
• 6.4: Use Pollard's \rho method to factor 341 with f(x) = x^2+1 mod n and x_0 = 3 =y_0.

Tut #10:

• 7.1: 1, 4, 10, 11
• 7.2: Find a primitve root modulo n when n = 17, 19, 23 respectively.

Tutorial #11.

• 7.3: 1, 2, 7
• 7.4: 1.

 Extra exercises Chapter 2 2.1, Page 13 : # 1-9, 21-23, 27-29 2.2, Page 24 : # 1-2, 5-7, 11 2.3, Page 31 : # 1-13, 15-16, 18 2.4, Page 36 : # 6-9 2.5, Page 44 : # 1 -9, 15, 19, 23. Chapter 3 3.1, Page 67 : # 1-9, 11-14. 3.2, Page 72 : # 1-8. 3.3, Page 80 : # 1-2. Chapter 4 4.1, page 107: # 1-9. 4.2, page 110: # 1-5. 4.3, page 116: #1, 3-6, 10-11. 4.4, page 119: #1-4 Midterm Chapter 5 5.1, page 131: # 1-3. 5.2, page 137: # 1-2. 5.3, page 143: # 2, 3, 6 Chapter 6 6.1, page 149: 1-2, 5, 8-11. 6.3, page 159, Exercise. Examples 6.3.2, 6.3.3, 6.3.4 6.4, page 165, Example 6.4.5, Exercises, Chapter 7 7.1, page 173: 1-12, 17. 7.2, page 181: 1, 3, 6. 7.3, page 185: 1-3, 7. 7.4, page 191: 1

 -->