Mathematics
116
Spring, 2010
Tu Th 11:10AM12:30 PM, 3109 Etcheverry Hall
 Course control number 54482

Current enrollment information
Prerequisites
Math 55 is the official prerequisite.
However, the essential mathematical content of this course overlaps
significantly with the three courses
Math 110, Math 113 and
Math 115. Experience with these courses is helpful, though not necessary.
The exercises in this course involve calculations that cannot be performed
by hand. At the beginning of the course, all that is needed is a calculator.
By the end, you will need to use Sage
or Magma to do
the homework. Since Sage is free, while Magma is a commercial product,
I urge you to download Sage and try it out as soon as possible.
You can also work with Sage online
instead of downloading it and using it locally.
Textbook
An
introduction to mathematical cryptography
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.
Be sure to consult the authors'
errata list
if you think that you've spotted an error.
The authors will be grateful to readers like us if we send them
additional corrections.
The book is available for purchase directly from
Springer
or from
Amazon.
However,
if you have an IP address that is associated with the campus and navigate to
http://www.springerlink.com/content/9780387779935,
you should see things like
Institutional Login
Recognized as:
University of California at Berkeley (41447457)
California Digital Library Springer (79802082)
and
Buy a Print Copy of this Book for $24.95 Including Shipping.
Further,
you can download the book, chapter by chapter, as a series
of eight .pdf files from the springerlink site. Accordingly, you can
have the book available to you on your laptop, desktop
or other digital device.
If you are not physically on campus but need access to electronic
resources for which UC is a subscriber, see
the
UC Berkeley Library Proxy Server help page
for some pointers.
Examinations
Please do not plan travel on these dates:
 First midterm exam, February 18, 2010 in class
(Questions
and skeletal solutions from last year's class and
the analogue from this
year's class), mean of scores 23.53, standard deviation 3.85;
 Next midterm exam, April 1, 2010 in class
(Questions
and skeletal solutions from last year's class
and the analogue from this
year's class);
cumulative distribution,
showing the 33 scores, ranging from 4 to 25;
 Final Exam, Thursday May 13, 2009 811 AM
in 3109 Etcheverry Hall
(Questions
and possible solutions from last year's class
and the analogue from this
year's class); mean = 30.3; standard deviation = 9.6.
The College's
20092010
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.
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, ending somewhere in Chapter 6
(the chapter on latticebased cryptography).
To follow the lecturebylecture pace of the course, please consult
the Math 116
iCal calendar.
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
 Basic linear algebra as in Math 54 and Math 110;
 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 from Chapter 1 due January 28, 2010:
1.5, 1.7bc, 1.8bd, 1.9ad, 1.10ad, 1.11bd, 1.13, 1.16 (all parts).
For some of these problems, it will be helpful to have an open Sage
notebook available for calcuations.
 Problems from Chapter 1 due February 4, 2010:
1.17fg, 1.18, 1.21, 1.23ac, 1.27, 1.28c, 1.30c, 1.31, 1.33, 1.34
 Problems due February 11, 2010:
2.4bc, 2.6, 2.8 (all parts), 2.10 (all parts), 2.17 (all parts), 2.19,
2.23 (all parts)
 Just a few problems due on February 18, 2010:
2.25, 2.28ab, 2.34a
 Not that many problems due on February 25, 2010:
2.38, 3.1ac, 3.2, 3.5a, 3.5b(i), 3.6; also use the PohligHellman
algorithm to find x such that 5^{x} is congruent to 67 mod 103.
 Problems due March 4, 2010: 3.8b, 3.9ab, 3.10, 3.13b (iii and iv),
3.14ace, 3.15, 3.18
 Problems due March 11, 2010:
3.21ab, 3.22bf, 3.23a, 3.24a, 3.25c, 3.39, 3.40
 Problems due March 18, 2010:
3.41bc, 4.2abd, 4.3de, 4.5 (all parts), 4.21, 4.22, 4.24, 4.27, 4.29
 Problems due March 32 (a.k.a. April Fool's Day), 2010:
4.32, 4.34a, 4.35, 4.37, 4.38, 4.39
 Problems due April 8, 2010:
4.42, 4.43, 4.47
 Problems due April 15, 2010 (Use sage as much as you want, but try to
do a few computations by hand to get a sense of what sage is doing):
5.1, 5.2 (including bonus if you can), 5.3, 5.4 (all parts, using sage),
5.5 (using the sage command list), 5.6, 5.7 (where the trace of
Frobenius is what I called a_{p}).
 Problems due April 22, 2010:
5.9, 5.10cd (use sage as appropriate, but try to follow the problem's
instructions), 5.11cd, 5.13, 5.15
 Last assignment, due May 4, 2010:
5.18b, 5.20 (using sage), 5.30 (using sage), 5.34, 5.39, 5.40
Grading
The scheme will be similar to that of last year's course, where
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.
In 2009, there were 29 students who took the final exam. Letter grades were
distributed as follows: 11 As, 15 Bs, 3 Cs.
Last Updated: