MATH220-20S1 (C) Semester One 2020

Discrete Mathematics and Cryptography

15 points

Details:
Start Date: Monday, 17 February 2020
End Date: Sunday, 21 June 2020
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Friday, 28 February 2020
  • Without academic penalty (including no fee refund): Friday, 29 May 2020

Description

Discrete mathematics underpins many areas of modern-day science. This course is an introduction to graph theory and cryptography, two central topics in discrete mathematics.

Discrete mathematics underpins many areas of modern-day science. This course is an introduction to graph theory and cryptography, two central topics in discrete mathematics, each having fundamental links to many branches of science. Graph theory underlies the solution to many problems in a variety of disciplines including operations research and computational biology. Cryptography has applications to all communications security, from state security to online banking and mobile phone conversations. This course is designed for mathematics and computer science students.

Topics covered:

Cryptography: Basic ideas and terminology of cryptography. Shift and affine ciphers. One-time pads. Basic properties of the integers. Euclid’s algorithm. Modular arithmetic. Public key ciphers. The RSA, Rabin and ElGamal ciphers. Diffie-Hellman key exchange. Arithmetic of polynomials over finite fields. Constructing finite fields. Linear and non-linear shift registers.

Graph theory: Concepts and terminology of graphs. Eulerian and Hamiltonian graphs. Complexity, polynomial-time and exponential-time algorithms. Chromatic polynomials. Matchings and Hall’s Marriage Theorem. The Greedy Algorithm. Directed graphs. Network flows.

Learning Outcomes

  • At the end of the course, students will:

  • Be familiar with  some of the old and modern cryptographic schemes and have developed the necessary mathematics to understand and analyse them.
  • Be familiar with some of the basic techniques of decipherment.
  • Have an understanding the field of graph theory with an emphasis on graph algorithms and proof techniques.

Pre-requisites

Restrictions

MATH221, MATH231

Timetable 2020

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01 Monday 11:00 - 12:00 Live Stream Available (23/3, 20/4, 4/5-25/5)
C2 Lecture Theatre (17/2-16/3)
17 Feb - 29 Mar
20 Apr - 26 Apr
4 May - 31 May
Lecture B
Activity Day Time Location Weeks
01 Wednesday 11:00 - 12:00 Live Stream Available (25/3, 22/4-27/5)
Meremere 108 Lecture Theatre (19/2-18/3)
17 Feb - 29 Mar
20 Apr - 31 May
Lecture C
Activity Day Time Location Weeks
01 Wednesday 13:00 - 14:00 Live Stream Available (25/3, 22/4-27/5)
C3 Lecture Theatre (19/2-18/3)
17 Feb - 29 Mar
20 Apr - 31 May
Tutorial A
Activity Day Time Location Weeks
01 Monday 09:00 - 10:00 24 Feb - 29 Mar
02 Monday 09:00 - 10:00 24 Feb - 29 Mar
03 Tuesday 16:00 - 17:00 Live Stream Available 24 Feb - 29 Mar
4 May - 31 May
04 Wednesday 14:00 - 15:00 Live Stream Available 24 Feb - 29 Mar
4 May - 31 May
05 Tuesday 09:00 - 10:00 Live Stream Available 24 Feb - 29 Mar
4 May - 31 May
06 Monday 14:00 - 15:00 Live Stream Available 24 Feb - 29 Mar
4 May - 31 May
07 Thursday 10:00 - 11:00 Live Stream Available 24 Feb - 22 Mar
4 May - 31 May
08 Thursday 14:00 - 15:00 Live Stream Available 24 Feb - 22 Mar
4 May - 31 May

Examination and Formal Tests

Test A
Activity Day Time Location Weeks
01 Friday 11:00 - 16:00 Check LEARN 20 Apr - 26 Apr

Course Coordinator

Charles Semple

Lecturers

Charles Semple and Magnus Bordewich

Assessment

To obtain a passing grade in this course you must pass the course as a whole (which requires an overall mark of 50% or more) and score at least 40% in the final exam.

Textbooks / Resources

There is no set text for the course. But there are several books that are recommended reading:
1. Buchmann, Introduction to Cryptography (2nd Edition)
2. Clark and Holton, A First Look at Graph Theory

Copies of these books will be on reserve in the Engineering and Physical Sciences Library. Also, there are a number of other good books on cryptography and graph theory in the library.

Indicative Fees

Domestic fee $780.00

International fee $4,250.00

* Fees include New Zealand GST and do not include any programme level discount or additional course related expenses.

For further information see Mathematics and Statistics.

All MATH220 Occurrences

  • MATH220-20S1 (C) Semester One 2020