Instructor:	Peter McNamara
Lectures:	Tuesdays and Thursdays, 2:15pm – 3:30pm in 380-380F (note the new room).
Office Hours:	Mon 2:30-3:30, Tue 1:15-2:13 or by appointment. In 380-382H.
Course Assistant:	Amy Pang,
CA Office Hours:	Tue 4-5, Wed 4-6pm. In 380-381F.
Writing in Major CA:	Brandon Levin,
CA Office Hours:	Wed 9 May, 1-3pm, Fri 11 May, 10-12. Sign up at this form.
Midterm dates:	Tue May 8. In class.
Final exam:	Mon 11 June, 7pm. In 380-380X Covers all topics covered in semester. For post-midterm topics, [TW] is mostly at the right level, only for primitive roots and Fourier transform is their treatment a bit sparse. Warning: [TW]'s generator matrix is the transpose of ours. Exam solutions.

Midterm

Solutions.

The Midterm is Tue May 8, in class, starting at 2:15pm sharp. Students are permitted to take in up to (1/8)m² of paper with notes (which may be two-sided).

Syllabus: The following topics are fair game: (for references, see the more detailed syllabus below)
General: Big O notation, time estimates for algorithms. Some mathematical maturity.
Number Theory: Divisibility, Euclidean algorithm, primes, Chinese remainder theorem, Fermat's Little theorem & Euler's generalisation, Continued Fractions, Legendre symbols.
RSA & factoring: RSA algorithm, low exponent attacks, Pollard's rho algorithm, Continued fraction factoring.
Miscellaneous: ISBN's, three-pass-protocol. Diffie-Hellman key exchange.

Practice problems: You can find exercises by looking in relevant sections of [TW] and [K]. [K]'s problems are often harder than [TW]'s. The exercise sections in [G] are generally of low quality.

Homework

Assignments may be handed in during class, or emailed to by 2:15pm sharp local time. If emailing, please put "Math 110 homework" in the subject.
Late homeworks will not be accepted (this is as much a courtesy to the grader as anything). Because of this policy, to accommodate unforseen circumstances such as sickness, everyone will have their lowest homework score for the quarter dropped.

Homework 1 (pdf). Due Thu Apr 12.
Homework 2 (pdf). Due Thu Apr 19.
Homework 3 (pdf). Due Thu Apr 26.
Homework 4 (pdf). Due Thu May 3.
Homework 5 (pdf). Due Thu May 24.
Homework 6 (pdf). Due Tuesday June 4.

Textbook

There is no set text. You may find the following books useful.

Week 1: Euclidean algorithm, primes, big O notation, bit operations esitmates. References: [TW] 3.1,3.2, [G] 9.1,9.2. Or [K] I.1,I.2.

Week 2: Modular Arithmetic, Diffie-Hellman key exchange. References: [TW] 3.3,3.4,3.5,3.6,7.4,18.1(ISBNs). Or [K], I.3,...

Week 3: RSA, continued fractions, three pass protocol. References: [TW] 6.1,6.2 Or many other places for RSA.

Week 4: Pollard's rho algorithm, Factor bases. References: [G] 24.1, [TW] 6.4.

Week 5: Continued fraction algorithm for prime factorisation, Quadratic residues. References: [K] V.4.3, [TW] 3.10.

Week 6: Midterm, quadratic reciprocity.

Week 7: Primitive roots, discrete Fourier transform, Quantum computing. References: ..., [TW] 19.

Week 8: Error Correcting Codes. [TW] 18.1-18.5.

Grading

Homework: (20%)
Writing in Major: (15%)
Midterm: (20%)
Final exam: (45%)

The Writing in the Major assignment is to produce a short essay on the topic of testing a number to determine whether or not it is prime. More precisely, give an exposition of the Miller-Rabin primality test. You should at least give a description of the algorithm, explain why failing the gest guarantees a number is composite, and why passing the test makes it "highly likely" that a number is prime (preferably explain why a composite number will pass the test with probability at most 1/4).

References: [TW] 6.3, [G] 16.6, [K] V.1.

The main point of this project is to concentrate on the exposition. Your paper should be 4-7 pages long and typed. The dominant typesetting system (and with good reason) in mathematics is LATEX, which is recommended.

Important dates: Tue May 15, typed draft due (can be handed in earlier for feedback, allow one week for a response), Tue May 22, drafts returned, Tue May 29, Final papers due.