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
    •  
    -->