"Guide for the Perplexed"

  http://en.wikipedia.org/wiki/The_Guide_for_the_Perplexed

/--------------------------------------------------------\
Dear Number-theory Cryptographic Enthusiasts   (Spring 2013)

For Monday's exam, in addition to everything else, you
should know, cold:

* How to solve all the quiz problems on
    http://math.ufl.edu/~squash/NT/NT2013g/quizzes-Cryp.2013g.pdf
  that are relevant to what we've covered so far.

* How to precisely STATE, and rigorously PROVE:
FLiT;
EFT;
Wilson's Thm  [involution ideas];
Legendre Symbol Thm (LST) parts (a,b,c) -and you should be able
  to state part (d).  [More involution ideas.]
  Note that if you use a term, e.g, "8Near", you must be able
  to rigorously /define/ it.
CRT.
Applications of CRT to finding roots of polynomials.  To
 speeding up RSA.
The Fusion Algorithm, and prove why it works.
All of the DEFINITIONS and material in:
    http://math.ufl.edu/~squash/PrNt/nt-review.pdf
  except for the irreducible/prime distinction.
That the multiplicative group of a finite field is cyclic.  Be
  able to compute a generator for Phi(p), when p is a small
  prime, e.g p<40.
How to prove, for a codeword set, that weak-UD implies UD.

* Know how to state:
  Kraft-McMillan Thm.
  The thm characterising the SOTS primes.
  The thm characterising the cyclicish numbers.


* Know the defn of:
(Totally) Multiplicative fnc, and several examples.
  Semigroup.  Group.  Abelian group.  Ring.  Commutative ring.  Field.
Know examples of each that is not an example of the next.
Zero-divisor in a ring; unit in a ring.
Cyclic group.  Cartesian product of groups.  Know examples of
  finite groups which are not cyclic.
Short certificate of <property X>.  Be able to give an example
  of a short certificate of compositeness, of primeness.
Defn of "group-isomorphism", "ring-isomorphism",
  "ring-homomorphism".
Mod-N primitive root.


Can apply the methods in:
    http://math.ufl.edu/~squash/PrNt/lightning-bolt.pdf
    http://math.ufl.edu/~squash/PrNt/nt-algorithms.pdf
    http://math.ufl.edu/~squash/PrNt/chinese-rem-thm.pdf
    http://math.ufl.edu/~squash/NT/chinese-RT.txt
    http://math.ufl.edu/~squash/NT/fuse-example.txt
    http://math.ufl.edu/~squash/NT/fibonn.txt
    http://math.ufl.edu/~squash/PrNt/jk-codes.pdf
      (except the entropy/distropy part.)


* Know how to rapidly implement the algorithms (that is, be able
  to APPLY the algorithm, and also be able to rigorously DESCRIBE
  the algorithm) for:
Know how to compute the mult-order of an elt in Phi(N).
Know how to compute Euler phi, and the Legendre symbol.
Encode/decode with affine-codes, breaking an affine-code given
  some plaintext with coded value.
Repeated-squaring.
LBolt.
Constructing Huffman codes.  Given a probability distribution,
  counting the number of Huffman trees, isomorphism classes of
  Huffman tress, the number of Huffman codes.
Know how to compute the MECL of a probability distribution.
  [Hint: Compute a Huffman code, then compute it ECL.]

* Know the mathematical description of:
RSA.
Discrete-Logarithm Problem (DLP).
Diffie-Hellman (DHP),
ElGamal (EGP).
Be able  to compute examples of each encode/decode/create.
Defn of "polynomial-time reducible" (one problem to another).
  Know how to prove that EGP and DHP are polytime equivalent, and
  each is polytime reducible to DLP.

\________________________________________________________/