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.
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 ``''.
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
- 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?
- 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!
- 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!
- 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!
- What does "NP" stand for in "P = NP"?
- 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?
- 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?
- Are there any problems that are so difficult
that they're not even in NP?
- How do you prove that a problem is in NP?
- What do you have to do to prove that a problem is NP Complete?
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?
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