Mathematics
116
Spring, 2009
Tu Th 11:10AM12:30 PM,
3 Evans Hall
 Course control number 54488

Current enrollment information
Prerequisites
Math 55 is the official prerequisite.
In addition,
it would be helpful to have had one or more of Math 110, Math 113,
Math 115. If you have had a couple of these upperdivision courses
but have never taken Math 55, that should be fine.
Textbook
An
introduction to mathematical cryptography
(Springer,
Amazon)
by
Hoffstein,
Pipher
and
Silverman.
Although this book describes itself as
``selfcontained,'' it
includes compact summaries of material from and abstract
and linear algebra and from number theory.
If you haven't had courses in these subjects, be prepared for moments
when you will need to digest a lot of material in a short amount of time.
As we go through the course, look ahead so that you can get a head
start on problematic passages.
Examinations
Please do not plan travel on these dates:
The registrar's
20082009
student calendar lists drop and gradechange deadlines.
You can still drop the course the day after the first midterm
and still change your
grading option to P/NP the day after the second midterm.
If you are contemplating these actions and think that you could benefit from
some information and/or advice, contact me immediately after the relevant exam.
Lectures
The catalog description (which was written
by me and/or Craig Evans)
is very terse:
"Construction and analysis of simple cryptosystems, public key
cryptography, RSA, signature schemes, key distribution, hash
functions, elliptic curves, and applications." The book covers
these topics and more.
I plan to follow the textbook, except that we'll likely have to omit
Chapter 6. (See Further notes for the instructor on page xv.)
My best guess is that we will have just finished
§3.3 (RSA) right before the first midterm and that we
will have begun to study elliptic curves before the second midterm.
After the second midterm, we will complete our discussion of
elliptic curves and then talk about digital signatures and "additional
topics."
As I stress above, the book can be viewed as selfcontained only because
it includes quick summaries of a number of topics that are best viewed
as inputs to a study of cryptography. Among these topics are
 Elementary number theory as presented in Math 55 and Math 115;
 Notsoelementary number theory (quadratic residues, quadratic
reciprocity), which is usually discussed in Math 115;
 Group theory as studied in Math 113;
 Commutative ring theory (including ideals and
quotient rings) as studied in Math 113;
 The basic theory of elliptic curves (not typically studied
in our undergraduate courses).
You can do yourself a big favor by checking out
these sections (§§1.21.4,
§2.5, §2.10, §3.1, §3.9, §§5.15.2)
ahead of time to see whether they are likely to be difficult
or easy for you. I will of course discuss them in class, but my
treatment will be a bit fast for people who have never thought about
the relevant subjects in their lives.
Recommended reading and other links
Homework
You may find the authors'
`Snippets from Selected Exercises'
helpful if you want to paste strings into a computer
application.
 Problems due January 29, 2009:
1.6b, 1.7d, 1.8d, 1.9cd, 1.10cd, 1.12a, 1.15d, 1.16h, 1.17fg, 1.24,
1.27, 1.28c, 1.29
 Problems due February 5, 2009:
1.30a, 1.31, 1.34, 2.4, 2.6, 2.7, 2.8, 2.10
 Problems due February 12, 2009:
2.17a, 2.18ab, 2.23 (all parts), 2.24 (all parts), 2.25 (both parts),
2.28a, 2.34ab, 2.35a, 2.37, 2.38, 2.39 with "some" replaced by "two"
 Problems due February 24, 2009:
2.40, 3.1ac, 3.4abc, 3.6, 3.8a, 3.9, 3.10, 3.13cde, 3.15, 3.21b, 3.23a, 3.25b
 Problems due March 3, 2009:
3.35, 3.38, 3.40, 3.41ab, 3.42, 4.1, 4.2, 4.5
 Problems due March 10, 2009
 Problems due Thursday, March 19:
4.31, 4.35, 4.37, 4.38, 4.42, 4.46
 Problems due Tuesday, April 7:
4.48, 4.51, 4.52, 4.53
plus the following
problem.
 Problems due April 14:
5.2, 5.5 (a,c), 5.7 (c,d), 5.8, 5.9, 5.11 (c), 5.13, 5.14,
5.18 (a,c)
 Problems due April 23:
5.20, 5.22 (ac), 5.26, 5.28, 5.30, 5.31, 5.32
 Problems due May 5:
5.34, 5.35, 5.36, 5.37, 5.38, 5.39, 5.40, 5.41,
7.1, 7.3, 7.4, 7.6, 7.7, 7.11
Grading
Each student had two midterm exam grades between 0 and 30; a final exam
grade between 0 and 50; and 11 homework scores, each between 0 and 12.
For each student, we computed a composite homework score between 0 and 114
by adding together the 9 highest homework grades and 1/2 of the second lowest
homework grade. We then calculated a composite course grade between 0 and 100
by adding together the average of the midterm exam grades, the final exam
grade and 20/114 times the composite homework score. The final letter
grades respected the ranking by composite course grade.
There were 29 students who took the final exam. Letter grades were
distributed as follows:
11 As, 15 Bs, 3 Cs.
Last Updated: