Mathematic Foundations of Information Security

Course Code: B63004Y

Course Name: Mathematic Foundations of Information Security

Credits: 2.0

Level: Undergraduate

Pre-requisite: Advanced Mathematics, Linear Algebra

Lecture Time: 40 hours

Course Description

This course mainly introduces information security with primary mathematical contents such as probability, number theory, algebra and computational complexity. This course is designed for undergraduates with major in information security and other relevant area. It provides solid and significant mathematical theories and skills, which can be as a foundation for more professional courses. This course contains large quantities of scattered knowledge ranging across several different fields. Students will learn from the professor in details and explore directions on their own.

Topics and Schedule

  1. Introduction of Probability (4 hrs)
    1. Fundamental operation, Conditional probability and Independence 
      1. Addition rule
      2. Multiplication rule
      3. Full probability formula
    2. Random variables, Probability distribution, Numerical characteristics
    3. Examples
      1. The birthday paradox
      2. Entropy
      3. Redundancy in natural language
  2. Fundamental Number theory (12hrs)
    1. Integer
      1. Conception of integer
      2. Greatest common divisors
      3. Euclidean algorithm
    2. Congruence and Remainder
      1. Ring theory and congruence properties
      2. Congruence Equation
      3. Chinese remainder theorem
      4. Euler theorem, Fermat theorem
      5. Quadratic Residue, Roots of integer modulo
    3. Typical algorithm of number theory
      1. Primality test
      2. Factorization
      3. RSA algorithm, Rabin algorithm
  3. Fundamental Algebra (12hrs)
    1. Set theory
      1. Subset, Quotient group
      2. Homomorphism and Isomorphism
      3. Lagrange theorem
      4. Cyclic group
    2. Finite field (Definition, Structure, Construction, Polynomial)
    3. Elliptic Curve
      1. Group construction using points on elliptic curve
      2. Discrete logarithm problem on elliptic curve
    4. Applications
      1. Linear feedback shift register
      2. Design of AES algorithm
  4. Basic of computational complexity theory (6 hrs)
    1. Turing machine
    2. Algorithm and computational complexity, Computability
    3. Complexity classes
      1. Reduction
      2. Complexity classes and their relationship
    4. Application in Theoretical Cryptography (Assumption and Reduction)
  5. Tests and Q-course (6 hrs)


A weekly homework will be given during weeks of the class. The homework will be graded and their scores will count for 20% of the total. At the middle and end of the semester, there will be mid-term and final examinations, which will count for 20% and 60% respectively. The full score of this course is 100.


This course uses handouts compiles by instructors.


[1]   DengguoFeng, Mathematic method and technology of Information Security, Tsinghua University Press, 2009-10

[2]   Gongliang Chen, Mathematical basis of Information Security, Tsinghua University Press, 2014

[3]   Dingyi Pei, Xiang Xu, Mathematical basis of Information Security, People Post Press, 2007