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

To get started...

...it would make sense to look over the material from the earlier review sheets for midterms — the final is cumulative, after all. [Although it will have a greater emphasis on the most recent material, which has not been on any midterms....] The specific things to know on the review sheets for midterm I and midterm II are still to be known for the final!

New Definitions

You should be able to give careful, complete, formal definitions of — and examples and know theorems involving — the following terms:
  1. primitive roots mod $n$
  2. the index of $b$ relative to $a$ [also called the discrete logarithm]
  3. the shared key/shared secrete in DHKE
  4. a Sophie Germain prime
  5. the Diffie Hellman problem

New Theorems, Conjectures, Algorithms, Problems, etc.

Please know careful, complete statements of the following:
  1. a theorem about natural numbers which are guaranteed to possess a primitive root
  2. a theorem about natural numbers which do not possess a primitive root
  3. a theorem relating the powers of an integer $a$ which are congruent to 1 mod $n$ and the order of $a$ mod $n$ (being Theorem 6.1.1).
  4. a theorem characterizing exactly which powers of an integer $a$ can be congruent mod $n$ (being Theorem 6.1.2).
  5. a theorem explaining how many primitive roots will exist, when there are any (being Theorem 6.3.3).
  6. a theorem about the existence of primitive roots of primes
  7. a theorem about the nonexistence of primitive roots of large powers of 2
  8. a theorem about the properties (like $\log$ but in mod $\phi(n)$) of the index (being Theorem 6.4.3).
  9. the Diffie-Hellman Key Exchange [DHKE] protocol
  10. the Diffie-Hellman Problem

New Things to know how to do

  1. compute orders of integers mod $n$
  2. find primitive roots (for small $n$) and use them to write any element of $(\ZZ/n\ZZ)^*$ as powers of the primitive root
  3. compute indices
  4. use indices to solve some modular polynomial equations
  5. perform the DHKE
  6. break the DHKE when the numbers involved are quite small
  7. prove simple statements about or using orders and indices
  8. give proofs of any of the theorems mentioned above (except the theorem about primitive roots of primes)

Format of the test

Be able to state — in full formality and five-part harmony — all the definitions from this review sheet and the review sheets for midterm I and for midterm II. You will be asked to do so for something like four or five out of seven or eight choices. You must also be able to give context, ideas, examples, etc., for each term you define!

You will also be asked to give full and formal statements of several of the theorems mentioned above &mdash and, again, from the two preview review sheets! &mdash as well as an example (or counterexample when some hypothesis is dropped) to which the theorem applies. You will also likely have to use those theorems in proving other statements.

There will then be a choice of around four out of seven or eight proof-y and/or computational things to do. Some of these will be proofs of the above theorems. Others will be to perform some cryptographic or cryptanalytic task with given data -- obviously, this data will be small, and you may use a calculator to help you with it. Finally, there will be some small statements, on the level of maxiquizzes, that you can choose to prove.