Math 5248: Cryptology and Number Theory
Spring 2019: Professor Andrew Odlyzko
Classes: MW 1:00 - 2:15, Vincent 113
Office Vincent Hall 511
Office hours (starting Mon Jan 28): Mon 5:30 - 7:00, Tue 2:00 - 5:30, and by appointment. However, always check this web page
before coming over, as on some days the hours may be restricted.
Textbook: "Cryptology and Number Theory" by Paul Garrett, available
at Alpha Print in Dinkytown (next to McDonald's), 1407 4th St SE, 612-379-8535.
Copies from previous years, produced by Alpha Print, are the same, and will work fine. However,
the first edition, printed by a regular publisher, has substantial differences, and
will not suffice.
You might find useful two textbooks that are available freely (and legally) online,
Victor Shoup's "A Computational Introduction to Number Theory and Algebra",
Shoup book, and William Stein's
"Elementary Number Theory: Primes, Congruences, and Secrets",
For popular historical accounts of cryptology, highly recommended sources
are Simon Singh, "The Code Book"
and (for much more detail) David Kahn, "The Codebreakers".
Computer algebra systems (very helpful, although not absolutely essential and not required): Maple, Mathematica,
available in Math computer labs, and also (for CSE undergrads) for free downloads at
CSE Labs. Some systems available for free on the Web, such
as Wolfram Alpha, will likely suffice. A calculator is advisable, even if you use a computer
algebra system, to reduce the tedium of computations.
Tests: No final, three 75-minute in-class mid-terms on Wed Feb 20, Wed Apr 3, and Mon May 6 (last class day).
Weekly homework assignments (usually, excluding mid-term days), due (usually) on Wednesdays, first one (a small
one) due Jan. 30.
Will be posted by the preceding Friday, and will (usually) cover material through the preceding Wednesday.
Always due at the beginning of a class, late homeworks will not be accepted.
If you can't make it to class, you can leave your homework in
my mailbox in Vincent 107, or email it to me (in either typeset or scanned form, PDF preferred).
You may work with others on homework
problems. However, you have to write up your solutions yourself, in your own words, to show you
understand the arguments.
Special challenge problems: There will be occasional challenge problems for extra credit.
No collaborations are permitted on those.
- phone 612-625-5413
- email: email@example.com (preferred and most reliable method)
Solutions to homework problems will be available through this site, usually posted the
evening of the day they are due. However, they will not be
live links, but URLs that you will have to paste into your browser to download (to keep
crawlers from downloading and archiving them). These are for your use only, do not put
them up on any web sites, Facebook pages, etc.
Tests will be open book; you may bring books, notes, and calculators, but no smart
phones, iPads, or other communication devices can be used, and you have to do all the work
Grades: homework will count for 30%, the three tests for 20%, 25%, and 25%, respectively.
Expected effort: This is a 4-credit course, so you are expected to devote 12 hours per week,
on average (including lectures).
Solution files for homeworks and midterms are provided for your personal use only. Do not
distribute them via email or posting anyplace.
Scholastic Conduct: Cheating or other misconduct will not be tolerated. The standard University
policies will be followed.
This course develops the basic ideas of cryptology and related areas
of number theory. Both symmetric and public key cryptosystems will
be introduced, as will random number generators and cryptographic
protocols. The basics of the Bitcoin cryptocurrency and of blockchain
technology will be covered
as an example of the application of the techniques developed in the
Homework assignments and other notes:
Each of these problems will be worth some number of points towards the
homework score (with fractional credit for partial solutions).
Suppose that the maximal score on all the regular homeworks is x, and you get y points
on those regular homeworks and z on the extra credit ones. Then your final homework score will be
the minimum of x and y+z.
Material covered on Wed Jan 23: sections 1.2, 1.4 - 1.6 of Chapter 1.
Due Mon Feb 4 (changed from original Wed Jan 30):
Textbook exercises 1.2.13, 1.2.17, 1.5.06, 1.5.09, and 1.6.01 (10 pts each).
Important note: In 1.2.17, assume that m is positive. (The claimed result is false if m is negative.
It would be a good (ungraded) exercise to find a counterexample to the claim of this problem when m is negative.)
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190204.pdf
Material covered on Mon Jan 28: sections 1.1 and 1.7, much of sections 26.1 and 26.2.
No office hours on Tue Jan 29 and no class on Wed Jan 30, due to U cancellations.
Due Wed Feb 6:
Textbook exercises 1.6.14, 26.2.08, 26.2.12, 26.2.29, and 26.2.30 (10 pts each)
Extra credit problem (20 pts): 26.2.17. (Reminder: no collaborations allowed on these problems.)
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190206.pdf
Material covered the week of Feb 4: rest of Chapter 1 and of sections 26.1 and 26.2, covered lightly
Chapter 8 and parts of Chapter 2.
Due Wed Feb 13:
Textbook exercises 1.6.09 (10 pts), 1.6.20, 1.7.14, 1.7.19, 1.7.21, 26.2.28, and 26.2.32 (15 pts each).
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190213.pdf
Material covered the week of Feb 11: a bit more material from Chapter 2, cover Chapter 4, start
on Chapter 6 (sections 6.1 and 6.4).
Material covered on Mon Feb 18: completed Chapter 6 (sections 6.2 and 6.3), lightly went over Chapter 5.
Wed Feb 20:
In class mid-term. Material to be covered: Material to be covered: chapters 1, 2, 4, and sections
6.1, 6.4, 26.2, and 26.3.
Open book; you may bring books, notes, and calculators, but no smart phones, iPads, or other communication devices can be used, and you have to do all the work yourself. Blue books will be available, but you do not have to use them.
No homework due this week. For practice on material that was not covered on homeworks,
work out textbook exercises 4.1.05, 4.1.08, 4.2.06,
4.5.01, 4.5.02 (although those two are poorly written, in 4.5.01
all the phrases about probabilities should be deleted, and they should instead be moved to 4.5.02),
6.1.02, and 6.4.01.
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190217.pdf
Mid-term: file http://www.dtc.umn.edu/~odlyzko/Math5248/exam4820190220.pdf
Mid-term solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190220.pdf
Office hours on Tue Feb 26: only 2:30 to 5:00.
Due Wed Feb 27:
Textbook exercises 6.2.07, 6.2.08, 6.3.06, 6.3.08, 26.2.25, and 26.2.31 (10 pts each).
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190227.pdf
Material covered the week of Feb 25: Much of chapters 9 and 10 (in a mixed-up order, leaving
for next week primarily sections 9.2 - 9.4, 9.7, 10.4 - 10.5, and 10.7 - 10.8).
Office hours on Tue Mar 5: 1:30 to 5:00 instead of 2:00 to 5:30.
Note: The method of Section 6.3 for computing multiplicative inverses does not
have to be used (or fully understood). The more primitive, but more intuitive,
method presented in class, where one builds the magic equation giving the gcd
of two integers by going backwards through the Euclidean algorithms, suffices.
No need to understand Section 9.8. Later on we'll learn another, more
intuitive method for this computation. The homework exercise for
this section is meant to take you through the cookbook approach,
to show it works. That can be done without a basic understanding
of why it works. (If you have had group theory, do try to read
that section, it might be understandable.)
Due Wed Mar 6:
Textbook exercises 9.1.06, 9.1.07, 9.5.04, 9.5.09,
9.6.03, 9.8.02, 10.2.07, and 10.3.01 (10 pts each), plus:
A1 (10 pts). Prove that x^5 + y^5 = 3 has no solution in integers x and y. (Hint: use modulo 11 arithmetic.)
A2 (10 pts). For which positive integer n < 100 is the Euler phi-function of n, which is the
size of (Z/n)^(x) (the set of reduced residue
classes mod n, those relatively prime to n) largest?
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190306.pdf
Material covered the week of Mar 4: completed chapters 9 and 10, started Chapter 7.
Due Wed Mar 13:
9.4.05 (you should use results of 9.4.01, even though you are not required to solve that problem),
9.7.05, 10.4.04, 10.4.06, 10.5.03, 10.8.02 and 10.8.08 (15 pts each, except 10.8.02 which is 10 pts),
where in 10.4.06 you are asked to
explain why the quadratic formula you have learned in high school does not solve
Extra credit problem (20 pts): 10.5.06. Remember you have to work on this on your own, no
collaborations allowed on this or other extra credit problems.
Solutions: file http://www.dtc.umn.edu/~odlyzko/Math5248/sol4820190313.pdf
Material covered the week of Mar 11: most of rest of Chapter 7 and a little of Chapter 14.
Due Wed Mar 27:
7.2.06 (10 pts), 7.2.10 (20 pts), 7.3.08 (10 pts), 7.3.12 (20 pts), 7.3.13 (25 pts), and
A1 (15 pts): Suppose that p is an odd prime, and g and h are two primitive roots mod p.
Can g*h ever be a primitive root?
Material to be covered the week of Mar 25: finish Chapter 7, cover Section 15.9, start Chapter 13.
Office hours on Tue Apr 2: 3:00 to 6:30 instead of 2:00 to 5:30.
Wed Apr 3:
In class mid-term. More to come.
Return to home page