Number Theory and Mathematical Cryptography

Some Resources

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 Notes on Codes (pdf) [CodeNotes] has a few embedded exercises.
In one convenient location: All 7 NT/Crypto quizzes so far (pdf). [Tuesday, 12Mar2019]
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.
Possibly: Along the way to developing cryptographic methods, we will solve a number of Diophantine equations, that is, algebraic equations where the only solutions that we allow are using integers. We will find all Pythagorean triples (a,b,c) of positive integers for which

a² + b² = c² .

We will discover that there is a two-parameter family of such solutions. See Pythagorean Triples (pdf) at Usually Useful Pamphlets.
Possibly: AKS polytime primality-test algorithm.
Possibly: Meshalkin Isomorphism code.

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

Time	Computer/Proj	Blackboard	Humor	E-Problems	Phone
?	?	?	?	?

Resources on The Web

If she saw this, (TAotDM) , WWSKnow?
The decipherment of a substitution cipher appears in The Gold Bug, by Edgar Allan Poe.
Wikipedia. See also Primality testing and links to original AKS article and improvement.
Historical Cryptography (Trinity College)>.
MathPages. (I haven't reviewed this.)
Sample chapters from the Handbook of Applied Cryptography. (I have not reviewed this book.)

Our textbook is An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics).

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)

The homepage of ... Mathematical Cryptography, with a link to its Errata sheet.
Here are links to this book at The Publisher's site and at Amazon.com.

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 2PM, 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.

Number Theory & Mathematical Cryptography

Some Resources

Approx. Syllabus

Resources on The Web

End-of-semester NT Individual Project