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:

 

WEEKS: 1-2:

·       Fundamentals of algorithm problem solving

·       Important problem types: Sorting, searching, graph

·       Fundamental data structures.

 

WEEKS: 3-5:

·       Analysis of algorithm efficiency

·       Time estimate for doing arithmetic: Big-O Notation

·       Number-theoretical algorithms and their complexity: Euclidean algorithm and Quadratic Residues

 

WEEKS: 6-7

·       Complexity theory in cryptography

·       Randomized algorithms and complexity classes P, NP, NP-completeness/hardness

·       Reducing one problem to another

 

WEEKS: 8-11:

·       Design and analysis techniques

·       Brute force and exhaustive search

·       Divide-and-conquer

·       Space and time trade-offs

·       Greedy technique

·       Dynamic programming

 

WEEKS: 12-14:

·       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.