JK focus
Articles
Fonts
JK Contradance calling
Dances/Composers (contradance)
Tunes/Bands (contradance)
L0 Contradance program
L1 Contradance program
L2 Contradance program
L3 Contradance program
L4 Contradance program
L5 Contradance program
Jonathan's dances
testing Misc
Navigation
Schedule
Teaching
StanZas
Michael Dyck's Contradance Index
LORs
Pamphlets
PASTCOURSES
SeLo 2018t
DfyQ 2018t
NumT 2018s
NumT 2016s
Combinatorics 20172018
DfyQ 2018g
Complex Vars 2017g
SeLo 2017g
NumT 2016s
NT & Math Crypto 2016g
Spr2019: MAT4930 2H22, Number Theory & Cryptography MWF7 [13:5514:45] LIT207 (CE)
Number Theory & Mathematical Cryptography
MAT4930 2H22 :
NT&MathCrypto counts as an Upperdivision mathelective.
This is a 1semester course for folks interested in Mathematical Cryptography
(major topic) and other aspects of Coding:
Data Compression and (time permitting)
Errorcorrecting codes.
We will also cover one example of an Isomorphism code.
It is accessible to anyone with an introductory NT course or
who has read the first chapter or two of a beginning NT text.
(I'd like you to know
What a prime number is,
and What mathematical induction is
and What an equivalence relation is.
Also helpful is how to “add two numbers mod N”,
and what the Euler phi function is.)
Good choices [all these books are in Marston Science Library,
on campus] for selfstudy are:
 Elementary Number Theory by James Strayer;
or
 A Friendly Introduction Number Theory by Joseph Silverman;
or
 Elementary Number Theory by David Burton;
or
 the text by Vanden Eynden.
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
classarchive URL
(I email this private URL directly to students).
 The NT/Crypto Microquizzes so far (pdf)
During AddDrop, we may have a
minitest of prerequisite knowledge.
The minitest counts for little, about
2%—4% of course grade, and selects some topics from:
:: Highschool knowledge
(formula for a line between two points, the Quadratic Formula,
intersecting a line with a parabola, etc.), and some
:: Sets&Logic ideas
(Equivalence relations, partial orders, binary operators,
induction, pigeonhole principle, cardinality, etc.)
:: Mathematical maturity
(Do you remember your basic calculus stuff? Do you remember how
to sum a geometric series?)
:: MathGreek alphabet (pdf),
which we will use in class frequently.
Available is a practice prereq.
 The historicallyimportant
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
classarchive 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
classparticipation grade.
Resources from a previous incarnation of the course
Approx. Syllabus
 A review of modular arithmetic.
 Versions of The Euclidean Algorithm (the
Lightning Bolt
alg).
 Possibly: LBolt over the Gaussian Integers.
Proving unique factorization in the Gaussian Integers. Using LBolt to write
certain primes as sumsoftwosquares.
 Euler phi function, Fermat's Little Thm.
EulerFermat Thm (EFT). The Legendre and Jacobi symbols.
 The RSA Cryptosystem.
 The Chinese Remainder Thm (CRT) and a brief introduction to Rings and Ringisomorphism.
 Huffman codes. Huffman's theorem on
minimum expected codinglength codes.
Uniquelydecodable codes and the KraftMcMillan theorem.
 DiffieHellman Cryptosystem.
Shank's Babystep Giantstep method for trying to break the DiffieHellman protocol.
 Pollardρ factorization algorithm.
DescentfromtheTop algorithm for computing the modM mult. order of an element.
 Possibly: Pollard's p1
factorization algorithm.
 MillerRabin algorithm. Possibly: Polytime testing whether N is a primepower.
 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^{2} + b^{2} = c^{2} .
We will discover that there is a twoparameter family of such solutions.
See Pythagorean Triples (pdf)
at
Usually Useful Pamphlets.
 Possibly: AKS polytime primalitytest 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
MULTIPLICATIVECIPHER: 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
AFFINECIPHER: 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 
EProblems 
Phone 
? 
? 
? 
? 
? 
Endofsemester 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 2PM, Thur., 25Apr2019.
The project must be carefully typed,
but diagrams may be handdrawn.
At all times have a paper copy you can handin; I do
NOT accept
electronic versions.
Print out a copy each day, so that you always have the latest version to
handin; 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.
JK Home page