"Guide for the Perplexed"
http://en.wikipedia.org/wiki/The_Guide_for_the_Perplexed
/--------------------------------------------------------\
Dear Number-theory Cryptographic Enthusiasts
For Monday's exam, in addition to everything else, you
should know, cold:
* How to solve all the quiz problems on
http://www.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://www.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 . 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://www.math.ufl.edu/~squash/PrNt/lightning-bolt.pdf
http://www.math.ufl.edu/~squash/PrNt/nt-algorithms.pdf
http://www.math.ufl.edu/~squash/PrNt/chinese-rem-thm.pdf
http://www.math.ufl.edu/~squash/NT/chinese-RT.txt
http://www.math.ufl.edu/~squash/NT/fuse-example.txt
http://www.math.ufl.edu/~squash/NT/fibonn.txt
http://www.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.
\________________________________________________________/