Course Objectives: The aim of the course is to present the basic topics in algorithms and complexity needed in cryptography. The fundamental algorithms in cryptography will be introduced and their complexities will be studied.
Course Learning Outcomes: Students are going to be familiar with the design and analysis of algorithms used in cryptography. They will be able to compute the complexities of the algorithms and to design new algorithms with the improved complexities.
Weekly Outline/Tentative Course Schedule:
· Fundamentals of algorithm problem solving
· Important problem types: Sorting, searching, graph
· Fundamental data structures.
· Analysis of algorithm efficiency
· Time estimate for doing arithmetic: Big-O Notation
· Number-theoretical algorithms and their complexity: Euclidean algorithm and Quadratic Residues
· Complexity theory in cryptography
· Randomized algorithms and complexity classes P, NP, NP-completeness/hardness
· Reducing one problem to another
· Design and analysis techniques
· Brute force and exhaustive search
· Space and time trade-offs
· Greedy technique
· Dynamic programming
· Selected algorithms and their complexity analysis: Multiplication of large integers and matrices, FFT computations
· Arithmetic circuits
· Parallel computation
Required Textbook/s & Readings:
· N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag , 2nd edition, 1994.
· N. Koblitz: Algebraic Aspects of Cryptography, Vol.3, Algorithms and Computation in Mathematics, Springer-Verlag, 1998.
· Anany Levitin, Introduction to the design and analysis of algorithms, Pearson, 2012
· Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2009
· Douglas Stinson: Cryptography: Theory and Practice. CRC Press, Inc, 1996.