Final Review Sheet for
Colorado State University, Pueblo
Math 319 — Number Theory — Spring 2014

Definitions

1. primitive root
2. index/discrete logarithm
3. Diffie-Hellman Problem [DHP]
4. Sophie Germain prime

Theorems, Conjectures, and Algorithms

1. a theorem about the order of an element $a\in(\ZZ/n\ZZ)$ dividing any $k\in\NN$ iff $a^k\equiv1\pmod{n}$
2. a theorem about how when working with powers of an element $a\in(\ZZ/n\ZZ)^*$, the powers should be thought of as in $\ZZ/\operatorname{ord}_n(a)\ZZ$
3. a theorem about orders of powers of an element
4. Gauss's Theorem on Sums of Euler's Function
5. a theorem about how many primitive roots there will be, assuming there is at least one
6. a theorem about existence of primitive roots modulo primes
7. a theorem about algebraic properties of indices
8. Diffie-Hellman Key Exchange [DHKE]
9. ElGamal Cryptosystem
10. ElGamal Digital Signature

Things to know how to do

1. find/work with orders of elements
2. find primitive roots
3. compute/work with indices
4. solve congruence equations using index methods
5. DHKE with someone
6. encrypt/decrypt/sign/verify using ElGamal

Format of the test

1. First, you will be asked to state — in full formality and five-part harmony (i.e., give context and examples) — something like 5 or 6 definitions from the course.
2. Next, you will be asked to state — again in full formality and five-part harmony (i.e., give context and examples) — something like 4 or 5 theorems/lemmata/algorithms from the course.
3. Then you will be asked to prove 2 or 3 out of twice as many of the lemmata/propositions/theorems from the course.
4. You will turn in the above part of the exam, and be given in return a printout of much of the course textbook along with the last part of the exam.
5. The last part will then be something like 4 or 5 problems, out of roughly twice as many, to do, similar in difficulty and content to homework and maxiquiz problems -- proofs and computations: make sure you know how to do the things to know how to do from this and the previous two review web pages.
   In response to requests, here are some proof techniques which you definitely should know and be comfortable using, for this section of the final:
   • induction: follow the steps clearly and formally
   • something where you have to use the fact that $\exists n,m\in\ZZ$ such that $na+mb=\operatorname{gcd}(a,b)$
   • something where you have to use various things we know about orders of elements of $(\ZZ/n\ZZ)^*$
   • using a big name theorem, like the DA, the CRT, the FTA, FLT, Euclid's Lemma, and Euler's, Gauss's, Lagrange's, or Wilson's Theorem
   Come to think of it, those are all absolutely fundamental to what we should have accomplished in the course so will all definitely be crucial steps in problems on the final.