Goto: Prof. King's page at Univ. of Florida.
Or: JK Homepage.

Modified:
Tuesday, 02Aug2016
Printed:
Saturday, 21Sep2019

Page:
http://squash.1gainesville.com/Include/thispage.shtml

Spr2019: MAT4930 2H22 17706, Number Theory & Cryptography MWF7 [13:55-14:45] LIT207 (CE)

(Previous versions of
[Spring 2016]
and
[Spring 2013]
and
[Spring 2011]
NT&MC
have nice photos of the class.)

The
#### End-of-semester NT Individual Project

The
IP (pdf),
is due, slid
u
n
d
e
r
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

My dog ate my homework.)

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

- 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

in the notes.*SOTS* - 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*.^{n} - 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 33*x*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* (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 responsibleto get all Notes / Announcements / TheWholeNineYards from a classmate, or several. All my classes have a substantial class-participation grade.

- 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

Various math czars who help out.

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

? | ? | ? | ? | ? |

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).

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.

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.

Have a great summer, folks! Stop by in the Autumn 2019.