WHAT YOU SHOULD STUDY! The easy answer is everything. However, the main things you should look at are the previous exams, the previous practice exam/study material, and the ``Since the 12-Week Exam'' section below. Especially, look over the sample questions for the ``Since the 12-Week'' material.

# Since the 12-Week Exam

## Number Theoretic Algorithms

Essentially we have three ``number theoretic'' algorithms that we covered:
Exponentiation
We covered ``divide and conquer'' exponentiation early on in the semester, but we really started needing it with our RSA implementation. What additional improvements can you make when you want to compute ?
GCD
What's interesting about our GCD algorithm historically? Whom is it named after? Know the algorithm and how to use it!
Extended GCD
If the gcd of two numbers and is , then it turns out that there exist two numbers and such that . The extended GCD algorithm returns not only the gcd , but also and . If I give you psuedo-code to jog your memory, you should be able to perform the algorithm on small numbers. You should also know how this helps you to compute multiplicative inverses ``''.

## RSA Algorithm

You should know this algorithm!
Key Generation
How are keys generated?
Encryption/Decryption
How do we encrypt and decrypt?
Security
What is RSA's security based on? Why is it difficult to crack? What would you have to do to your implementation to foil Mr. Lemerande's RSA cracking program? Why can't we be sure that we may always rely on RSA to provide secure communications?
Authenication
How can RSA provide authenticated communication (i.e. a ``digital signature'')?
Export Controls with Cryptology
We talked about this stuff, and you should know the basics -- who controls this? what constitutes exporting? can you export cryptographic technology?

## P, NP, Reduction, NP-Completeness

P
What's the definition of P?
NP
What's the definition of NP? Be able to show that a problem is in NP! What does ``NP'' stand for?
P vs NP
What's the big P vs. NP question? True/false/Nobody Knows: if a problem is in P it is also in NP? True/false/Nobody Knows: if a problem is in NP it is also in P?
Reduction
If I reduce problem to problem , which one is harder?
NP-Complete
What does it mean for a problem to be ``NP-Complete''? Give me an example of an NP-Complete problem. How could NP-Complete problems help you prove P = NP?

## Some Sample Questions

1. True or false or nobody knows ;-) You have to be selling (i.e. recieving money for) a cryptography product overseas to fall under the export control regulations for cryptographic software? Explain!
2. True or false or nobody knows - It is impossible to solve the 0/1 Knapsack problem in time polynomial in the input size of the problem. Explain!
3. True or false or nobody knows - Since Dr. Brown can crack 32-bit RSA encryption in about a minute, he could crack 128-bit RSA in about four minutes. Explain!
4. What does "NP" stand for in "P = NP"?
5. Suppose I have a function
```
ZZ power(ZZ x, ZZ e);
```
That uses divide and conquer exponentiation. We know that this function only does recursive calls, so I think it should be able to compute power(123456789,9876543210) very quickly -- in about steps, which is about 33. Unfortunately, it takes forever. Where's the flaw in my logic?
6. Would I have to change anything in our RSA implementations if I wanted to encode 8 characters at a time, rather than 3? What would I do differently?
7. Are there any problems that are so difficult that they're not even in NP?
8. How do you prove that a problem is in NP?
9. What do you have to do to prove that a problem is NP Complete?

# Before the 12-Week Exam

## Asymptotic Analysis

What do , , and mean? What does it mean when I say, for example, that Quicksort is in the worst case? What's the difference between saying ``Algorithm is in the worst case'' and saying ``Algorithm is in the worst case?

## Algorithms you should know

 Algorithm Best Worst Average technique Insertion Sort Bubble Sort Sequential Search Binary Search depends Divide & Conquer D & C Exponentiation Divide & Conquer MergeSort Divide & Conquer QuickSort Divide & Conquer QuickSelect Divide & Conquer Matrix Chain Multiplication Memoization/Dynamic Programming Longest Common Subsequence Memoization/Dynamic Programming Simple Scheduling Greedy Algorithms Superincreasing Knapsack Greedy Algorithms Huffman Trees Greedy Algorithms Prim's Algorithm Greedy Algorithms Mulitpop Stack Amortized Time Binary Counter Amortized Time Extensible Array Amortized Time Modular exponentiation Number Theoretic Algs Euclidean GCD Number Theoretic Algs Extended GCD Number Theoretic Algs

• Graph Algorithms -- Breadth-first, Depth-first, Shortest Path, Cycle Detection, Topological Sort.
• Huffman Encoding -- Uses greedy algorithms for tree construction, DFA's (the tree is a DFA!), expression trees and postfix as the basis for encoding the tree as a sequence of 0's and 1's.
• 0/1 Knapsack-based public key cryptosystem
• RSA
• , , and -completeness

Christopher W Brown
2001-04-26