News

For this, our final week of the course:
x-period for review on Tuesday;
last day of classes Wednesday;
tutorial Thursday evening as usual;
Prof. Pomerance will not have office hours after Wednesday;
TA Pollack will have office hours on Wednesday and Friday as usual;
Final Exam will be on Friday at 3 pm in Bradley 102 (not our usual room).

Studying: For earlier material in the course there is ample material, with old study problems, old tests, and assignments.
Here are a few thoughts regarding Chapter 6 material:
We will discuss Section 6.4 on Wednesday; it would help to read this beforehand.
Describe how to implement the "powermod" algorithm to compute a^b (mod n) in the context of elliptic curve groups; that is to compute bP in an elliptic curve group, given an element P and a positive integer b.
Describe in detail an algorithm that computes -P, given an elliptic curve and a point P on it.
Give the formulas for the homogeneous coordinates of P+Q, given points P, Q in homogeneous form on an elliptic curve. Give your answer with no fractions visible.

Abstract

The theme of the course is number theory and its application to public-key cryptography. In a somewhat fast manner we will develop the necessary tools in number theory, including prime numbers, modular arithmetic, and elliptic curves. We will apply these tools to public-key cryptography, which is the backbone of security on the Internet. It is assumed that students have taken some algebra and so are familiar with basic algebraic structures. It will also be assumed that students are comfortable with proofs.

Classes

Bradley Hall, Room 105
Lectures: Monday-Wednesday-Friday 12:30pm--1:35pm (12 hour)
X-period: Tuesday 1:00pm--1:50pm

Staff

Instructor:

Carl Pomerance -- 102 Choate House (corner of Choate and North Main)
Office hours: Tuesday, Wednesday, Thursday 9:00am--10:00am and by arrangement at other times.

TA:

Paul Pollack
Tutorials: Thursdays, 7:00 pm--8:00 pm, starting April 6, in Bradley 103.
Office hours: Wednesday & Friday (beginning April 5) 10:00 am--11:00 am, Bradley Hall 1-H

Grader:

Jonathan Huang

Textbook

Elementary Number Theory, by William Stein
(required)

This book is available free online at http://modular.washington.edu/ent/ and hard copies are available for $8.75 from the Dartmouth Copy Center in Thayer Hall.

Grading

Homework 20%, two mid term exams each 20%, final exam 40%. As much as possible, grades will be based on demonstrated knowledge. However relative performance may be used as a criterion for increasing grades, and grade borderlines will be chosen to place a relatively small number of students on borderlines. At the end of the term, the lowest of your 4 grades (hw, midterms, final) will be dropped, except if your final exam is your lowest grade, in which case the weight of the final exam will be halved. (So, if one of the midterms or hw is dropped, then the remaining 3 grades have weights 25, 25, 50; while if the final is the lowest, the four grades have equal weight 25, 25, 25, 25.)

Homework

Homework is due at the start of the class period on the due date. Late homework is generally not accepted unless there is a prior arrangement.

Past assignments

Homework due May 26: Book problems 6.2, 6.3, 6.4, 6.7

Homework due on Friday, May 12.
Book problems 4.6 through 4.9.
Also: Show that for any nonzero integer a, there are infinitely primes p with (a/p)=1.

Homework due Friday, May 5:
Problems 4.1, 4.2, 4.3 in the book.
(4) Suppose d^2 |p-1, where p is prime. Suppose g is a primitive root modulo p,
we have the nonzero residue t (mod p), and t &equiv g^a (mod p).
We do not know a, but we wish to compute the residue a (mod d^2).
Show how this can be done as two separate problems of size d, so taking O(d)
steps if one searches naively, or O(d^{1/2}) steps if one uses baby steps/giant steps.

Homework due Monday, May 1:
(1) Do the 3 problems in Chapter 3.
(2) Show that if p is a prime and d|p-1, then a nonzero residue u (mod p) is a d-th power mod p (that is, a residue of the form u &equiv x^d ( mod p)), if and only if u^{(p-1)/d} &equiv 1 (mod p).
(3) Show that if p is a prime and d|p-1, g is a primitive root mod p, and u is a nonzero residue mod p, then exactly one of u, ug, ..., ug^{d-1} is a d-th power mod p.
(4) Explain how you can use the previous two exercises to do the following: You are trying to solve the discrete log problem g^a &equiv t (mod p). You are given the prime p, a nonzero residue t, and a primitive root g, so it is a you are looking for. You know that d|p-1. Give an algorithm to compute a (mod d) that should be fairly efficient if d is small. Explain why doing discrete logs for the prime p = 2311 is fairly easy.

Homework due Friday, April 14 (the assignment is complete):
Chapter 2, numbers 3, 6, 7, 17, 21, 9-12, 20, 23.

Homework due Friday, April 7 (assignment is complete):
(1) Say that a positive even number is "prime-even" if it cannot be written as the product of two smaller positive even numbers. Show that unique factorization into prime-evens fails for the positive even numbers.
(2) The book has the example of the ring Z[α], where α is a squareroot of -5. It claims that unique factorization is violated because 6 = (2)(3) = (1+α)(1-α). Assuming the only units in Z[α] are 1 and -1, prove the assertion that the two different looking factorizations of 6, involve different "irreducibles." (An irreducible is a nonzero element that cannot be factored into two factors unless at least one of the factors is a unit.)
(3) In the proof of the Division Theorem (Prop. 1.1.10) we are to look at the set of nonnegative numbers of the form a-nb. Show that if b is not 0, then n = -|a|b gives a nonnegative member of the set regardless of the signs of a and b.
(4) In this problem give proofs that do not rely on the Fundamental Theorem of Arithmetic. The letters a,b,c,d are integers.
(i) If gcd(a,b)=1 and d|a, prove that gcd(d,b)=1.
(ii) If ab|n prove that b|n.
(iii) If a|bc and gcd(a,b)=1, prove that a|c.
(iv) If a|n, b|n, and gcd(a,b)=1, prove that ab|n.
(5) Do the chapter 1 problems on page 20. Does the limit in problem 4 imply the following? If one chooses a random integer in [1,x], the probability that it is prime tends to 0 as x goes to infinity.

Exams

The two midterm exams will be held in our classroom, Bradley 105, on the evenings of April 19 and May 17 from 7:00pm to 9:00pm. These exams will be constructed so as to be doable in 60 minutes; the extra hour is to help you relax and not feel so rushed.

The final exam will be held on June 2 from 3:00pm to 6:00pm.

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's code or solutions, in whole or in part, is a violation of the Honor Code.

The honor principle applies to exams as follows: Students may not give or receive assistance of any kind on an exam from any person except the professor or someone explicitly designated by the professor to answer questions about the exam. Students may not use a computer during an exam, but they may use a calculator to help with simple arithmetic.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand.

Other

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.

I realize that some students may wish to take part in religious observances that fall during this academic term. Should you have a religious observance that conflicts with your participation in the course, please come speak with me before the end of the second week of the term to discuss appropriate accommodations.