Number Theory and Mathematical Cryptography

The

End-of-semester NT Individual Project

The IP (pdf), is due, slid u n d e r room 402 Little Hall my office door (Little Hall 402, Northeast corner) , no later than 3PM, Thur., 25Apr2019.

The project must be carefully typed, but diagrams may be hand-drawn.

At all times have a paper copy you can hand-in; I do NOT accept electronic versions. Print out a copy each day, so that you always have the latest version to hand-in; this, in case your printer or computer fails. (You are too old for My dog ate my homework.)

Please follow the guidelines on the Checklist (pdf, 3pages) to earn full credit.

Some Resources

Notes-in-progress on Fermat's SOTS (Sum-Of-Two-Squares) thm.
Slides showing how the Euclidean Algorithm writes a given N as a Sum Of Two Squares (pdf). Such an N is a SOTS in the notes.
Defn of the Jacobi symbol (Top // Bottom) starts on P.4 of Quadratic Reciprocity (pdf).
[It is preceded by a proof of Quadratic Reciprocity, and has proofs of the Eisenstein and Gauss Lemmata. You are only responsible for the statement of Quadratic Reciprocity, not its proof, and we did not cover the other two lemmas, but in case you are curious, they are in the pamphlet.]
There is a nice Wikipedia page on the Jacobi Symbol.
Hensel's Lemma (pdf), for a lifting a mod-p root of a polynomial, to be a root mod pⁿ.
Partial Theorem List (pdf) [LBolt. Irred vs. prime. FLiT. ERT. Wilson's thm. LST. Quadratic-reciprocity thm.] for Number Theory.
Intro to Multiplicative Functions (pdf) and convolution of number-theoretic functions, such as Euler-phi.
Our Notes on Codes (pdf) [CodeNotes] [Monday, 08Apr2019] has a few embedded exercises.
The Entropic Class-C now has all solns.
In one convenient location: All 10 NT/Crypto quizzes so far (pdf). [Monday, 22Apr2019]
Home-B [due BoC, Wedn., 20Mar.] has all solns. It was followed [Friday, 22Mar.] by the nifty Class-B, [now with all solns] whose last problem arose from class-discussion.
Our syllabus has exam dates.
For the curious, Huffman's original 1952 paper (pdf).
Empirical Entropy of English. (Claude Shannon's experiment); needs Java enabled, to run.
Brain-cell exercise was fun with Home-A, and Class-A --which now with all solns, as well as two challenge problems (ta, Jeffrey).
The important Chinese Remainder Theorem (pdf) [CRT] tells us the structure of Zed_M.
We also need facts from Finite fields have cyclic multiplicative groups (pdf). This pamphlet also proves the Primitive Root Thm, and Korselt's Thm characterizing the Carmichael numbers.
The Euclidean algorithm can be presented in table-form; I call this form the Lightning-bolt algorithm (pdf), because the update-rule looks like a lightning-bolt (used thrice). Here is a practice sheet for LBolt (pdf).

The first page of Algorithms in Number Theory (pdf), uses LBolt iteratively to compute the GCD of a list of integers, together with its list of Bézout multipliers. Page 2 uses LBolt to solve linear congruences: Find all x where 33x is mod-114 congruent to 18.
xkcd Cryptography
A topics guide (txt) for one of the exams from an earlier course.
Repeated-squaring examples.
:: Math-Greek alphabet (pdf).
The historically-important Meshalkin Example (pdf) of two isomorphic Bernoulli processes, with different distributions yet the same entropy.

Our Teaching Page has useful information for students in all of my classes. It has my schedule, LOR guidelines, and Usually Useful Pamphlets. One of them is the Checklist The checklist

(pdf) which gives pointers on what I consider to be good mathematical writing. Further information is at our class-archive URL (I email this private URL directly to students).

In all of my courses, attendance is absolutely required (excepting illness and religious holidays). In the unfortunate event that you miss a class, you are responsible to get all Notes / Announcements / TheWholeNineYards from a classmate, or several. All my classes have a substantial class-participation grade.

Approx. Syllabus

A review of modular arithmetic.
Versions of The Euclidean Algorithm (the Lightning Bolt alg).
Euler phi function, Fermat's Little Thm. Euler-Fermat Thm (EFT). The Legendre and Jacobi symbols.
The RSA Cryptosystem.
The Chinese Remainder Thm (CRT) and a brief introduction to Rings and Ring-isomorphism.
Huffman codes. Huffman's theorem on minimum expected coding-length codes. Uniquely-decodable codes and the Kraft-McMillan theorem.
Diffie-Hellman Cryptosystem. Shank's Baby-step Giant-step method for trying to break the Diffie-Hellman protocol.
Pollard-ρ factorization algorithm. Descent-from-the-Top algorithm for computing the mod-M mult. order of an element.
Miller-Rabin algorithm.
Multiplicative functions. Dirichlet convolution.
Hamming codes. Shannon source-coding thm. Shannon's Noisy-channel thm.

ENCODING: a b c d e f g h i j k l m n o p q r s t u v w x y z ' . ? ! , 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Three Examples of simple ciphers: CAESAR: Shift of 9: a b c d e f g h i j k l m n o p q r s t u v w x y z ' . ? ! , 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0 1 2 3 4 5 6 7 8 MULTIPLICATIVE-CIPHER: Mult by 5: a b c d e f g h i j k l m n o p q r s t u v w x y z ' . ? ! , 0 5 10 15 20 25 30 3 8 13 18 23 28 1 6 11 16 21 26 31 4 9 14 19 24 29 2 7 12 17 22 27 AFFINE-CIPHER: Mult by 5, then add 9. x |-> [5*x]+9 (mod 32) a b c d e f g h i j k l m n o p q r s t u v w x y z ' . ? ! , 9 14 19 24 29 2 7 12 17 22 27 0 5 10 15 20 25 30 3 8 13 18 23 28 1 6 11 16 21 26 31 4

Authors:	Jeffrey Hoffstein, Jill Pipher, J.H. Silverman	ISBN:	978-0-387-77993-5
Year:	2008	Publisher:	Springer
Marston:	QA268 .H64 2008	Electronic:	Chap. 1 and Chap. 2, Diffie-Hellman, etc. (Free for UF students)

Number Theory & Mathematical Cryptography

End-of-semester NT Individual Project

Some Resources

Approx. Syllabus

Resources on The Web