Mathematics
116
Spring, 2012
Tu Th 9:40AM11:00 AM, 9 Evans Hall
 Course control number 54284

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, check ahead for 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
California Digital Library Springer
and
BUY A (Softcover) PRINT COPY (USD $24.95).
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, Valentine's Day in class
(Questions
and skeletal solutions from 2009 and
the analogue from 2010
year's class);
maximum possible score = 40, mean = 30.6, standard deviation = 6.6.
There are now
questions and skeletal solutions for February's
exam.
 Next midterm exam, March 20, 2012 in class
(Questions
and skeletal solutions from 2009
and the analogue from
2010);
maximum possible score = 35,
mean = 22.2, standard deviation = 6.2.
There are now
questions and skeletal solutions for the
second midterm exam.
 Final Exam, Wednesday May 9, 2012 11:30AM2:30PM
in 9 Evans;
maximum possible score = 50, mean = 34.47, standard deviation = 9.53.
(Questions
and possible solutions from 2009
and the analogue from 2010
year's class.)
The L&S
student
calendar lists drop and gradechange deadlines.
The drop deadline is February 17, while the deadline to change
grading options is March 23.
If all goes well, midterms will be returned to you on February 16
and March 22.
Lectures
The catalog description
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 for the most part but will base
a few lectures on other documents.
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
Some of these are left over from the 2010 list. I added
additional links during the course and will continue as
appropriate.
 Mining your
Ps and Qs by
Nadia Heninger
et. al.
 Factoring integers
using elliptic curves over Q by X. Li and J. Zeng (July, 2012).
 What
on earth is `index calculus'? by
Claus Diem.
 Thinking, fast and slow
by Daniel Kahneman.
This book teaches us that we are not wired for probability.
Even professionals and other experts make gross errors in estimating
probabilities, especially conditional probabilities.
 Chances
are, NY Times blog by
Steven
Strogatz about conditional probability.
 The 16th workshop on Elliptic
Curve Cryptography, ECC 2012
 Heuristics on
pairingfriendly elliptic curves by
John Boxall.
 A
one round protocol for tripartite DiffieHellman by
Antoine Joux
 The
Cunningham project.
 The
development of the number field sieve:

Integer
Factoring by
Arjen
K. Lenstra (may require UC Berkeley credentials).
 Wikipedia's
page on
Lnotation.
 Gary L. Miller's
article
Riemann's
hypothesis and tests for primality.
This is reference [78] in our textbook.
 Sage
for Power Users
by
William Stein.
 An amazing
research article about RSA key generation in the wild; you might
start by reading the NY Times's
account
of the findings.
 A blog post
by
Nadia Heninger
reassuring us that RSA keys for serious web sites
are much more secure than the New York Times suggested.
 Cover
and Decomposition Index Calculus on Elliptic Curves made practical.

Civil War Diary Code:
break this code and you'll make the UC Berkeley history department
very happy!
 SAGE download
 Introduction
to Cryptography
by
Johannes
Buchmann

Cryptography:
theory and practice
by
Doug Stinson
 Making, Breaking Codes:
introduction to cryptology by
Paul Garrett

Introduction
to Cryptography with Coding Theory
by
Wade Trappe
and
Lawrence C. Washington

Elliptic curve cryptography:
The serpentine course of a paradigm shift
by
Ann Hibner Koblitz,
Neal Koblitz and
Alfred Menezes
 Primality
Testing in Polynomial Time
by Martin
Dietzfelbinger
(reference [34] in our book)
 John M.
Pollard's home page
 Smooth
numbers and the quadratic sieve, a talk by
Carl Pomerance
 Table
of the smallest
Carmichael numbers
with a given number of prime factors
from the
OnLine
Encyclopedia of Integer Sequences
 Poker
hand frequences, prepared for my
Fall, 1997 Math 55
class
by GSI
Loren
Looger; note that the number of hands having three of a kind is
54912, rather than the 54972 that's indicated!
 The Hot Hand in Basketball by Gilovich, Vallone and Tversky
 The
nostats allstar by
Michael Lewis

CAN YOU
CRACK A CODE? Try Your Hand at Cryptanalysis from our friends
at the FBI.

Simon Singh's
The Code Book
 A cipher to Thomas Jefferson by Lawren Smithline
(requires a subscription to
American Scientist,
but UCB is an institutional
subscriber)
 A new
approach to generating random numbers
 The March 2010 issue
of the Notices of the American
Mathematical Society is devoted to cryptography.
 A tale of
two sieves by Carl
Pomerance
 Cryptography by
David R. Kohel
 Exploring
Cryptography Using the Sage Computer Algebra System, honors thesis
by Minh Van Nguyen
 Nova:
the Spy Factory
Homework
You may find the authors'
Snippets from Selected Exercises
helpful if you want to paste strings into a computer
application.
 Assignment due January 26, 2012
 Assignment due February 2, 2012
 Assignment due February 9, 2012:
Problems 2.34, 2.35, 2.36, 2.37, 2.38 (primitive root = multiplicative
generator), 2.39.
Also:
Let K and F be the fields of order 7^{3} defined
respectively
by the
cubic polynomials
x^3 + 6x^2 + 5x + 3
and
x^3 + 2x^2 + 3.
Find an explicit isomorphism of fields from K to F.
 Assignment due February 16, 2012: write out complete bulletproof
solutions to the
six exam questions. For computations, it's OK to use
sage. Also, answer this supplemental question: Suppose you know
that Alice and Bob have
published RSA moduli that share a prime factor. How can you
factor the two moduli?
(Although this assignment is due at 9:40AM on Thursday, I will
accept homework papers until 5PM on Friday. To hand in an assignment
once class ends on Thursday, you can slide your paper under my door
(885 Evans Hall).)
 Assignment due February 23, 2012:
Problems 2.23(c,d),
3.1 (b,e), 3.5, 3.6, 3.8(d), 3.9(a,b), 3.10, 3.12, 3.13(b, part iv),
3.14(g), 3.16 (but use prime_pi
of sage instead of writing your own
program).
 Assignment due March 1, 2012:
Problems 3.18, 3.19, 3.21c, 3.23d, 3.24c, 3.25d, 3.26e, 3.28.
Feel free to use sage on these problems as appropriate.
 Assignment due March 8, 2012:
Problems
3.31, 3.32, 3.34 (make sage do the work!), 3.38, 3.39, 3.41, 3.42.
 Assignment due March 15, 2012:
Problems 5.1, 5.2, 5.3, 5.4cd, 5.5de, 5.6a.
In all cases, use sage as much as possible.
You might want to look at
my notebook on elliptic
curves over finite fields
and Jared Weinstein's
notebook on elliptic curves over the rational field.
 Assignment due March 22, 2012: write out complete bulletproof
solutions to the
exam questions. For computations, it's OK to use
sage.
(Although this assignment is due at 9:40AM on Thursday, I will
accept homework papers until 5PM on Friday. To hand in an assignment
once class ends on Thursday, you can slide your paper under my door
(885 Evans Hall).)
 Assignment due April 5, 2012:
5.7d, 5.10d (use the algorithm but let sage do the intermediate
computations), 5.13, 2.10, 5.14, 5.18cd, 5.20 (using sage), 5.22abc
 Assignment due April 12, 2012:
Carry out the computations of problem 5.30 using weil_pairing
of sage.
Do problems 5.34 and 5.35, referring to the book's description
of a distortion map for the latter problem.
Continue with problems 5.37, 5.38, 5.39, 5.40, 5.41.
We are ahead of the lectures here, so you'll need to look at sections
5.8 and 5.9.
 Assignment due April 19, 2012:
Problems 5.42 and 5.43; problems 4.4,
4.21, 4.22, 4.24, 4.25, 4.27, 4.28, 4.29.
 Assignment due April 26, 2012:
Problems 4.33, 4.34, 4.35, 4.36, 4.38, 4.39 (using sage), 4.41 (a calculus problem!), 4.46.
Grading
Course grades
will be based on a composite numerical score
that is intended to weight
the course components roughly as follows:
midterm exams 15% each, homework
25%, final exam 45%.
I have taught this course twice before.
 In 2009, there were 29 students who took the final exam.
Letter grades were distributed as follows: 11 As, 15 Bs, 3 Cs.
 In 2010, I had 35 students. There were 14 As, 17 Bs, 3 Cs and 1 F.
 In this class, 32 students took the final exam.
They received 10 A's, 17 B's and 5 C's.
You might want to read
the student evaluations
for this course.
Last Updated: