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

Modified:
Friday, 12Nov2021
Printed:
Friday, 21Jan2022

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 following is from
Wikipedia, the free encyclopedia

Cryptography(orcryptology; derived from Greekκρυπτός kryptós"hidden," and the verbγράφω gráfo"write") is the study of message secrecy. In modern times, it has become a branch of information theory, as the mathematical study of information......

Steganography(i.e., hiding even the existence of a message so as to keep it confidential) was also first developed in ancient times. An early example, from Herodotus, concealed a message - a tattoo on a slave's shaved head - by regrown hair. More modern examples of steganography include the use of invisible ink, microdots, and digital watermarks to conceal information .Ciphertexts produced by classical ciphers always reveal statistical information about the plaintext, which can often be used to break them. After the Arab discovery of frequency analysis (around the year 1000), nearly all such ciphers became more or less readily breakable by an informed attacker. ... Essentially all ciphers remained vulnerable to cryptanalysis using this technique until the invention of the polyalphabetic cipher by Leon Battista Alberti around the year 1467. Alberti's innovation was to use different ciphers (ie, substitution alphabets) for various parts of a message (often each successive plaintext letter). He also invented what was probably the first automatic cipher device, a wheel which implemented a partial realization of his invention. In the polyalphabetic Vigenère cipher, encryption uses a key word, which controls letter substitution depending on which letter of the key word is used.

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

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.

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.

- Modular arithmetic.
- Versions of The Euclidean Algorithm (the
Lightning Bolt

alg). - Euler phi function, Fermat's Little Thm. Euler-Fermat Thm (EFT).
- 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 allPythagorean triples

(a,b,c) of positive integers for which

a^{2}+ b^{2}= c^{2}.

We will discover that there is a two-parameter family of such solutions. SeePythagorean Triples (pdf)

at Usually Useful Pamphlets.*Possibly*: LBolt over the Gaussian Integers. Proving unique factorization in the Gaussian Integers. Using LBolt to write certain primes as sums-of-two-squares.*Possibly*: The Legendre and Jacobi symbols.*Possibly*: Meshalkin Isomorphism code.*Ambitious*: Shannon source-coding thm. Shannon's Noisy-channel thm.- Ambitious: AKS polytime primality-test algorithm.
- Ambitious: Distribution of Primes: Chebyshev thm, Bertrand's postulate, PNT (Prime Number Thm).

- xkcd Cryptography
- :: Math-Greek alphabet (pdf).
- Our Notes on Codes (pdf) [CodeNotes]
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.- Repeated-squaring examples.
- 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* - 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. - Brain-cell exercise was fun with Home-A,
and Class-A
--which now with
*all*solns, as well as two challenge problems (ta, Jeffrey). *In one convenient location*: All ten NT/Crypto quizzes so far (pdf).- 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.
- The Entropic Class-C now has all solns.
- 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.
- Partial Theorem List (pdf) [LBolt. Irred vs. prime. FLiT. ERT. Wilson's thm. LST. Quadratic-reciprocity thm.] for Number Theory.
- A topics guide (txt) for one of the exams from an earlier course.
- The historically-important Meshalkin Example (pdf) of two isomorphic Bernoulli processes, with different distributions yet the same entropy.
- 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} - Intro to Multiplicative Functions (pdf) and convolution of number-theoretic functions, such as Euler-phi.

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

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.

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