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