Math 5248: Cryptology and Number Theory
Spring 2018: Professor Andrew Odlyzko
Classes: MW 1:00  2:15, Vincent 113
Office Vincent Hall 511
 phone 6126255413
 email: odlyzko@umn.edu (preferred and most reliable method)
Office hours: 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., 6123798535.
Used copies from previous years, produced by Alpha Print, are the same. However,
the first edition, printed by the publisher, has substantial differences, and
would not suffice.
Additional material:
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",
Stein book.
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 75minute inclass midterms on Wed Feb 14, Wed Mar 28, and Wed May 2 (last class day).
Weekly homework assignments (usually, excluding midterm days), due (usually) on Wednesdays, first one (a small
one) due Jan. 24.
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.

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.
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
yourself.
Grades: homework will count for 30%, the three tests for 20%, 25%, and 25%, respectively.
Expected effort: This is a 4credit 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.
General remarks:
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 will be covered
as an example of the application of the techniques developed in the
course.
Homework assignments and other notes:

Material covered on Jan 17: Sections 1.1, 1.2, 1.4  1.6 of Chapter 1 (with a few
results to be covered on Monday).

Due Wed Jan 24:

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

Material covered the week of Jan 22: finish Chapter 1, cover most of sections 26.1 and 26.2 and Chapter 8.

Due Wed Jan 31:

Textbook exercises 1.6.04, 1.6.09, 1.6.14, 1.7.14, 1.7.19, 1.7.21, 26.2.08, 26.2.12, 26.2.29, and 26.2.30 (10 pts each).

Extra credit problem (20 pts): 26.2.17.

Material covered the week of Jan 29: Chapter 2, sections 4.1 and 4.2.

Due Wed Feb 7:

Textbook exercises 2.1.10, 2.1.12, 2.2.04, 2.2.05, 4.1.05, 4.1.08 (15 pts each), 4.2.06 (10 pts).

Material to be covered the week of Feb 5: Complete Chapter 4, lightly go over Chapter 5, do Chapter 6.

Material to be covered on Mon Feb 12: Start chapters 9 and 10 (in a mixedup order).

Office hours on Tue Feb 13 will be 1:30  5:00.

Wed Feb 14:

In class midterm. Material to be covered: chapters 1, 2, 4, 6 (but no need to
learn the "little cleverer" method of Section 6.3), and sections 26.1 and 26.2.

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.4.01, 4.4.12, 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, 6.2.07, 6.2.08, 6.3.06, 6.3.08, and 6.4.01.

Due Wed Feb 21:

Textbook exercises 9.1.06, 9.1.07, 9.5.04, and 9.5.09 (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 phifunction of n, which is the
size of (Z/n)^(x) (the set of reduced residue
classes mod n, those relatively prime to n) largest?

A3 (10 pts). Solve the modular equation 2101*x + 1111 = 0 mod 2513.

Material to be covered the week of Feb 19: Rest of chapters 9 and 10.

Due Wed Feb 28:

Textbook exercises 9.6.03, 9.7.05, 9.8.02, 10.1.02, 10.2.07, 10.3.01,
10.4.04, 10.4.06, 10.8.02 and 10.8.08 (10 pts each), where in 10.4.06 you are asked to
explain why the quadratic formula you have learned in high school does not solve
this equation.

Extra credit problem (20 pts): 9.6.12. Remember you have to work on this on your own, no
collaborations on this or other extra credit problems.

Material covered the week of Feb 26: Cover remaining few pieces of chapters 9 and 10,
start Chapter 7.

Due Wed March 7:

Textbook exercises 7.2.06, 7.2.09, 7.2.10, 7.3.08, 7.3.12, 7.3.13, 9.4.01,
9.4.05 (you should use results of 9.4.01, even if you have not succeeded in solving that problem),
and 10.5.03 (10 pts each, except for 20 pts for 7.2.09).

Extra credit problem (20 pts): 10.5.06. Remember you have to work on this on your own, no
collaborations on this or other extra credit problems.

Material to be covered the week of March 5: Finish Chapter 7, cover (briefly) Chapter 14, start Chapter 13.

Due Wed March 21:

Textbook exercises 7.5.03, 13.1.04, and 13.1.08 (20 pts each), as well as:

A1 (20 pts): Show that if k is a positive integer such that 6*k+1, 12*k+1, and 18*k+1 are all
prime, then n = (6*k+1)*(12*k+1)*(18*k+1) is a Carmichael number. (There is additional material
on Carmichael numbers in Section 17.2.)

A2 (20 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?

Extra credit problem (20 pts): Consider a knapsack cipher of the type described in Section 7.6,
where the superincreasing sequence is given by a_i = 2^i, and the public weights c_i are a permutation
of the (t*a_i)%m. Show how to break this scheme.
As before, no collaborations on this problem are allowed.

Material covered the week of March 19: Rest of Chapter 13, chapters 12 and 17, and most of sections 18.3  18.5.

Wed Mar 28:

In class midterm. Material to be covered: chapters 7 (although only sections 15), 9, 10, 12, 13, 17,
and sections 18.3  18.5.

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 12.5.11, 12.5.13, 12.5.14, 13.4.01 (but do it just for 561), 13.6.01,
13.6.05, and 18.3.03.

Material to be covered on Mon March 26: rest of Chapter 18.

Material to be covered the week of April 2: Chapters 19 and 20.

Due Wed April 4:

Textbook exercises 18.1.03 and 18.2.04 (20 pts each), as well as:

A1. Compute efficiently 77^20180404 modulo 525 (20 pts).

Tue April 10: Office hours will be 2:00  5:00 only.

Material to be covered the week of April 9: Sections 24.3 and 24.4,
the notes on Lagrange polynomial
interpolation formula and secret sharing schemes, written up in
file http://www.dtc.umn.edu/~odlyzko/Math5248/lagrange20101203.pdf, and early parts of Chapter 15.

Due Wed April 11:

Textbook exercises 20.1.11 and 20.2.07 (20 pts each).
Please note that the textbook has a slight mistake in the description of
the babystep giantstep algorithm. In the first display
equation on p. 273, floor(sqrt(n)) should be replaced by ceiling(sqrt(n))
(i.e., the least integer equal to or larger than n^(1/2)).
Also, there is a certain twist to 20.2.07 that you might find surprising.

1. (15 pts) Are there integers x such that 5 * ( 45 * x^2 + 2 )^1111 = 33 mod 77, and if so,
find at least one.

2. (5 pts) Express (1, 0, 1) as a linear combination over the integers mod 2 of (1, 1, 1), (0, 1, 1),
and (1, 1, 0).

3. (15 pts) Find a linear dependency over the integers mod 2 of the row vectors (0 1 1 0 1 1 0 1 1),
(1 0 1 0 1 0 1 0 1), (0 1 0 0 1 1 1 0 0), (1 0 1 1 0 0 1 1 1), and (1 0 0 1 0 0 0 0 0)
(where I have dropped commas, the symbols are all 0 and 1, and these are all binary row vectors of
length 9); that is, find a linear combination of those vectors that is the zero vector.

4. (25 pts) Factor the integer n = 13231 (= 101 * 131) by taking advantage of the relations
(all modulo n): 122^2 = 3 * 19 * 29, 124^2 = 3 * 5 * 11 * 13, 125^2 = 2 * 3^2 * 7 * 19,
126^2 = 5 * 23^2, 127^2 = 2 * 3^2 * 7 * 23, 129^2 = 2 * 5 * 11 * 31,
134^2 = 3^3 * 5^2 * 7, 136^2 = 3^4 * 5 * 13, 139^2 = 2 * 3 * 5 * 7 * 29,
141^2 = 2 * 5^2 * 7 * 19, 146^2 = 3 * 5 * 7^2 * 11, 149^2 = 2 * 3 * 5 * 13 * 23
and linear algebra on exponents of the prime factorizations.

Extra credit problem (20 pts): Suppose we modified the Pollard rho method, so the
iteration would be f(x) = x^2 mod n instead of f(x) = x^2 + 2 mod n.
How well would it perform, and why? (You are encouraged to try some moderately
large examples using a computer.)

Material to be covered the week of April 16: Chapter 15 and the notes on Lagrange polynomial
interpolation formula and secret sharing schemes, written up in
file http://www.dtc.umn.edu/~odlyzko/Math5248/lagrange20101203.pdf.

Due Wed April 18:

Textbook exercises 15.2.01 and 15.2.04 (15 pts each).
 1 (15 pts) Over Z/7, reduce the polynomial 2*x^8 + 5*x^7 + x^5 + 4*x^4 + 2*x^3 + x + 6
modulo 3*x^5 + 2*x^4 + x^3 + 6*x + 5.
 2 (15 pts) Determine the irreducible polynomials over Z/3 of degrees 1, 2, and 3.
 3 (15 pts) Factor the polynomial 3*x^3 + 2*x^2 + x + 2 into irreducible ones over Z/5.
 4 (25 pts) Over Z/11, find the gcd of the polynomials f(x) = 9*x^4 + x^3 + 7*x^2 + 10*x + 2
and g(x) = 2*x^3 + 7*x^2 + 10*x + 10
and express it as a linear combination, with polynomial coefficients, of f(x) and g(x).

Extra credit problem (20 pts): Let f(x) = a_d x^d + a_(d1) x^(d1) + ... + a_0 be a polynomial
of degree d over Z/p. Show that
f(x) is irreducible if and only if g(x) = a_0 x^d + a_1 x^(d1) + ... + a_d is irreducible.

Material to be covered the week of April 23: Parts of Chapter 16
and the notes on polynomial irreducibility testing and factorization,
file http://www.dtc.umn.edu/~odlyzko/Math5248/polyfactor20141127.pdf
and on random number generation,
file http://www.dtc.umn.edu/~odlyzko/Math5248/polyrng20180418.pdf

A few important typos in the book: In Section 16.9, up to the Theorem that says "A polynomial
P in F_p[x] of degree n is primitive ...," most of the occurrences of lower case n should
be replaced by N = p^n  1. The polynomial P is to be of degree n, but the condition in
the basic definition, and later, is that P divides x^N  1 but does not divide x^t  1
for any t with 0 < t < N.

The missing result from the Wed April 18 class, that an irreducible polynomial
f(x) of degree k does not divide x^(p^r1)  1 for any r < k will be presented Mon Apr 23.

Due Wed April 25:

Textbook exercise 15.3.01 (25 pts).
 1 (20 pts) Find the simplest counterexample you can to the Lemma on p. 195 of the
textbook, about LCM of polynomials.
 2 (25 pts) Formulate the Chinese Remainder Theorem for polynomials over Z/p and prove it.
 3 (15 pts) How many linear factors does the polynomial x^((p1)/2)  1 have over Z/p
for an odd prime p?
 4 (15 pts) A teacher wants to distribute a secret (which is an integer between 1 and 100)
to a class of 10 girls and 29 boys. He regards the girls as twice as reliable as boys, so
wants a scheme in which (i) any 3 girls, or (ii) any 2 girls and any 2 boys, or (iii) any girl
and any 4 boys, or (iv) any 6 boys, can get together and recover the secret, but no smaller
group (such as any girl and any 3 boys, or any 5 boys) can do it. Describe how to set up
such a scheme. (You don't have to write out the gory details, but use mathematical notation
to make clear what you are doing. Elegance of solution will count in assigning grades.)

Extra credit problem (20 pts): Prove (starting from scratch, without looking it up online or in books)
that if mu(d) is the Moebius function, defined on p. 156 of the textbook,
then sum of mu(d) over all the divisors d of a positive integer n equals 1 if n = 1,
and equals 0 if n > 1.

Mon Apr 30: Last regular class. Primarily hash functions and applications of methods
from this class to Bitcoin. (It you are interested in a light introduction to cryptocurrencies
such as Bitcoin, you can watch the video of my presentation at the 2015 TEDx held here
at the U, YouTube video on cryptocurrencies.)

Class evaluation forms will be handed
out to be completed after the (shortened) lecture.

Wed May 2: last session, inclass midterm.
 Material to be covered on midterm: chapters 15, 16 (but no need to master all the theory,
only the materials needed for the exercises listed below), 18 (first 2 sections), 19, 20,
24 (last 2 sections),
and the notes posted on this page about
Lagrange polynomial interpolation and secret sharing
and polynomial irreducibility testing and factorization.
 Same rules as on other exams: open book, ..., 75 minutes.
 No homework due this week. For practice on material that was not covered on homeworks,
work out exercises 16.3.01, 16.3.02, 16.4.01, 16.11.01, 16.11.03, and 16.12.01.
 Also, factor the polynomial x^5 + 2 x^2 + 2 x + 2 modulo 3.

Midterm and course grades should be available by Sat May 5, and will be emailed to everyone.
Up [
Return to home page
]