Number Theory and Cryptography
Fall 2003
Mathematics V3020 section 001
M, W 10:35-11:50 am
520 Mathematics Building
http://www.math.columbia.edu/~glass/fall03/
Darren Glass
Office: 516 Mathematics Building
Office Phone: (212) 854-5135
glass@math.columbia.edu
The best way to get in touch with me is by email. I am an email addict.
Announcements
Check this part of the website regularly for announcements.
- 12/16/03 - All the grade data about the final exam is now posted
- 12/05/03 - Here is the list of times and
places you can get your questions answered for the final
- 12/02/03 - New Largest
Prime Number found!
- 11/26/03 - this is the movie we watched in
class today, in case you are one of the people who took off early for
Turkey Day. Or if you were in class and are just dying to see it again
and again.
- 11/19/03 - By popular request, here is some
statistical information about the grades. Do not second-guess me and
try to convert these into letter grades on your own. If you have
questions about how they will convert into letter grades you should talk
to me.
- 11/19/03 - For problem 1 of HW 8 if you would prefer to answer the
question mod 37 go ahead. This will let you work directly with a prime
though the numbers get uglier. Its your call. (Better yet, do both!)
- 11/17/03 - Here is the
list of the 207 different proofs of quadratic reciprocity.
- 11/10/03 - Here
are the details on the talk Alex is giving tomorrow evening.
- 11/05/03 - There were some problems in the first draft of HW7. They
have been corrected as of 4:15pm today.
- 10/31/03 - Despite the day off, I will hold my normal office hours on
Monday. I may also have some time on Tuesday if you wish to discuss the
homework then. Email me to let me know.
- 10/31/03 - If you went to the Agrawal lecture and want to write a
summary of what he talked about for extra credit, you must turn it in to
me by the end of next week -- November 7th.
- 10/30/03 - I did not get as far as I had intended in Wednesday's
lecture, so you do NOT have to do Silverman 21.3 for homework this week.
It will be part of next week's assignment instead.
- 10/22/03 - If you missed your chance to fill out a midsemester
evaluation, or if you have more you want to say, feel free to fill out another one.
- 10/15/03 - Here is the announcement of the lecture
by Agrawal. Let me know if you are interested in going. Relatedly,
here is an article about the primality test from the
Wall Street Journal
- 10/15/03 - I have posted below a practice midterm.
- 10/14/03 - Here is the original paper that
explains the Agrawal-Kayal-Saxena primality test. You may also want
to check out this very
nice exposition by Kedlaya of various primality tests.
- 10/09/03 - Note that you will not be able to do problems 5 or 6 of HW
Set 5 until after Monday's lecture. You should be able to do the others
now.
- 10/07/03 - On problem one of homework set four you may assume that k
is an integer. If you can say more in the case where k is not an integer,
go ahead. But don't worry about anything other than k being an integer.
- 10/06/03 - www.mersenne.org is
the home of the Great Internet Mersenne Prime Search and the website I was
talking about today in class.
- 10/01/03 - Several of the topics we have discussed related to
cryptography are not in Silverman. You might want to read the article by
Boneh and.or the relevant sections of Kumandari-Romero or Garrett.
- 09/30/03 - More solutions have been added below due to popular
request.
- 09/29/03 - Here
is the article by Dan Boneh that I discussed in class today.
- 09/29/03 - Several of you noted that Alex took points off if you
didn't prove the conjecture on Problem Number 7, even though it did not
explicitly ask you to. In general you should assume that there may be
points if you prove any conjecture that a problem asks you to make. In
this case, we decided to "lower the bar" -- in other words, your scores
say they are out of 35 but they are actually going to be viewed as out of
33. So anyone who did prove the conjecture got extra credit.
- 09/29/03 - No office hours today. Email me if you want to schedule
extra appointments later in the week.
- 09/22/03 - I have started posting partial solutions to old homework
sets below. If there are particular problems you would like to see
solutions written up to, drop me an email to let me know.
- 09/21/03 - Several of you have asked what I mean by a 'square number'
on the homework set. A square number mod m is a number that can be
written as n^2 mod m for some m. For example, mod 3 we have seen that 0^2
= 0, 1^2 = 1 and 2^2 = 1 (mod 3). So the square numbers mod 3 are 0 and 1
(and NOT 2).
- 09/16/03 - I have written up a solution to The
Prime Triplet Problem.
- 09/09/03 - A couple of you emailed me asking me if it was ok to buy
the first edition of the textbook rather than the second edition. Here's my answer.
- 09/08/03 - I have posted below a calendar for the course, listing
what topics I have covered/will cover each day.
- 09/02/03 - Problem Set One is posted below.
Course Information
Content
Number Theory is, in my rather biased opinion, the most beautiful area of
mathematics. It is one of the oldest area of mathematics, and in recent
years a great number of applications to cryptography (and other things)
have been found. Some of the topics will include: divisbility, modular
arithmetic, prime numbers, public key cryptography, and quadratic
reciprocity.
A list of what I have done each day can be found at this website
Textbook
A Friendly Introduction to Number Theory (Second Edition - Joseph
Silverman. (available at Amazon
and ADDALL
as well as your local bookstore) will be our primary textbook. I will
supplement it with other material, and will post those references here as
we go along.
I often find it helpful to look at multiple books to get a variety of
viewpoints on the same material. If you wish to do this, some of the
books I reccomend are:
- Elementary Number Theory - Underwood Dudley
- An introduction to Number Theory - PD Schumer
- Number Theory with Computer Applications - Ramanujachary
Kumanduri & Christina Romero
- Making, Breaking Codes - Paul Garrett
- Lecture
Notes on Cryptography - Shafi Goldwasser & Mihir Bellare
Office Hours and Other Help
Number Theory is not an easy subject, and it is almost certain that you
will need help during the semester. Please do not hesitate to take
advantage of the various forms of help that we provide. The Columbia Help
Room is Mathematics 406. I will be there on Wednesdays from 3-4, but
you may go there anytime it is open to have your questions answered.
The TA for this course is Alex Kontorovich (alexk@math.columbia.edu).
He will be in the Columbia help room on Mondays and Wednesdays from 5-6
and Tuesdays from 10-11.
I will be in my office (516 Mathematics) on Mondays from 1:30-3 and
by appointment.
Grading
25% - Midterm (Oct. 22 in-class)
35% - Final (TBA)
40% - Homework and Class Participation
Midterm
This exam will be in class, closed book, etc. The exam will be on October
22nd in class. I chose this date in part to avoid conflicting with any
religious holidays, etc. If there is going to be a conflict you must let
me know as soon as you do. No makeup exams will be given without prior
arrangement.
- Practice Midterm - DVI PDF
- Partial Solutions to the Practice Midterm DVI PDF
- Midterm - DVI PDF
Final
The final exam will be a three hour cumulative exam which is scheduled for
Monday December 15th from 9am-noon. Please make any travel plans
accordingly.
Homework
Homework will be assigned roughly once a week. You are encouraged to
discuss homework with each other, but you must turn in your own work. If
you aren't sure exactly where the boundary lies, please ask me rather than
make assumptions. Late homework will be penalized unless prior permission
has been obtained from the professor. All homework will be graded not
only on correctness, but also on how well you communicate and explain your
answers. Mathematics is a process, not a final answer, and your work
should reflect that.
For many of you, this will be the first course where you are writing
proofs. Learning to do this well is a slow and difficult process. Some
hints (written by Allison Pacelli) which you may find helpful are here. A more
detailed introduction to writing for math courses can be found on
Annalisa Crannell's webpage
- Problem Set One (due 9/10) - PDF or DVI. Solutions in PDF or DVI
- Problem Set Two (due 9/17) - PDF not DVI.
Solutions in PDF or DVI
- Problem Set Three (due 9/24) - PDF or DVI. Solutions in PDF or DVI
- Problem Set Four (due 10/8) - PDF or DVI. Solutions in PDF or DVI
- Problem Set Five (due 10/15) - PDF or DVI. Solutions in PDF or DVI
- Problem Set Six (due 11/5) - PDF or DVI. Solutions in PDF or DVI
- Problem Set Seven (due 11/12) - PDF or DVI. Solutions in PDF not DVI
- Problem Set Eight (due 11/26) - PDF or DVI Solutions in PDF or DVI
- Redemption Assignment (also due 11/26) - HTML
- Problem Set Nine (due 12/8) - PDF or DVI Solutions in PDF or DVI
Other Resources
Norm Thompson