Steven Rudich is an Associate Professor of Computer Science at Carnegie Mellon University. His research interests are in computational complexity theory and the mathematical foundations of cryptography. You can find out more about him from his web page:
This course contains ten lectures that develop the basic ideas behind modern cryptography and five lectures on special topics in discrete mathematics. The lectures are specially chosen to contain material that will transfer easily to the high school classroom. The special topics are chosen because they have been particularly well received by high school audiences.
Introduction to the problem of private communication over a public channel. The basic formal paradigm. Code making versus code breaking. An unbreakable code and perfect secrecy.
Sorting stacks of pancakes by reversing the top portion with a spatula. The notion of an algorithm. Counting the number of flips required to sort a stack of n pancakes. Upper and lower bounds on the pancake numbers. Inspiration versus perspiration.
What is the fastest way to raise a number to an integer power by repeated multiplication of previously obtained results? Upper and lower bounds. Repeated squaring method.
Elementary principles for counting large sets without enumerating them. The Correspondence Principle and the Multiplication Principle. Checking for mistakes using the Sleuth's Criterion. Counting Poker hands.
What is the nature of cryptography when the message is longer than the key? The RSA cryptosystem. the Diffie-Hellman cryptosystem. Public-key versus private-key cryptography.
The problem of finding a stable pairing among n boys and n girls given arbitrary preference lists for each individual. The traditional marriage algorithm. The naked mathematical truth about which sex has the upper hand in traditional dating.
Putting the pieces together. Private-key cryptography and one-way functions. Public-key cryptography and trapdoor-functions. The possibility of unbreakable codes based on the computational hardness of problems.
The simplest interesting computers: Finite Automata. A visual programming language that you can learn in five minutes. Cool programs. Inherent limitations of these machines. Cellular automata and the firing squad problem.
Finite fields. Counting the number of polynomials of degree d that pass through a given number of points. Shamir's secret sharing scheme. Application to nuclear missle launching.
How to compute the average salary of a group of people without anyone revealing any information about his/her salary. Zero-knowledge. Other surprises...