Lectures:

• Thursday 11 in CG93 
• Friday 9 in CLC202 
• Problems Class Tuesday 2pm in W103 weeks 1,3,5,7,9 

Contents:

Lecture 1 (Th 6.10.): Overview

Lecture 2 (Fr 7.10.): Properties of the integers; primes and divisibility.

Lecture 3 (Th 13.10.): Greatest common divisor, division algorithm, Euclidean algorithm.

Lecture 4 (Fr 14.10.) Fundamental Theorem of Arithmetic. Are there infinitely many primes?

Lecture 5 (Th 20.10.) Euler product. Primes in arithmetic progressions.

Lecture 6 (Fr 21.10.) The Prime Number Theorem and primes in arithmetic progression.

Lecture 7 (Th 27.10.) Prime Number Theorem, Riemann Hypothesis,

Lecture 8 (Fr 28.10.) Congruences, Arithmetic mod n, Towards Fermat's Little Theorem.

Lecture 9 (Th 3.11.) Fermat's Little Theorem, linear congruences, Euler-Fermat, Euler phi function.

Lecture 10 (Fr 4.11.) Wilson's Theorem, primality tests.

Lecture 11 (Th 10.11.) Chinese Remainder Theorem.

Lecture 12 (Fr 11.11.) Chinese Remainder Theorem, Applications, Modular exponentiation.

Lecture 13 (Th 17.11.) Diffie-Hellman key exchange, computing k-th roots modulo m, trapdoor function.

Lecture 14 (Fr 18.11.) Computing k-th roots modulo m (algorithm), RSA.

Lecture 15 (Th 24.11.) Attacking/cracking RSA. Factorization methods.

Lecture 16 (Fr 25.11.) Factoring with high probability. Towards primitive roots modulo a prime.

Lecture 17 (Th 1.12.) Primitive roots modulo a prime. Index calculus.

Lecture 18 (Fr 2.12.) Index calculus. Quadratic residues.

Lecture 19 (Th 8.12.) Legendre symbol, Euler's criterion.

Lecture 20 (Fr 9.12.) Quadratic reciprocity law.

Notes of all the lectures (updated 12.01.12). Here is a link to an elementary proof of the Prime Number Theorem by Zagier, following an idea of Newman (4 pages).

Assignments: 

Hand in on 13th October:  Sheet 1: Q2b), Q6b), Q8a).  

Hand in on 27th October:  Sheet 3: Q1), Q2b), Q3a), Q5c).  

Hand in on 10th November:  Sheet 4: Q2b), Q3(ii), Q4c), Q6).  

Hand in on 24th November:  Sheet 6: Q1a), Q2a), Q3a), Q5a).  

Hand in on 8th December:  from Sheet 7: [correction:] Q4), and from Sheet 8: Q1), Q2).  

Problems:

(Almost) every week a new sheet will be added, and eventually solutions will be given to most of the problems.

Hint for Sheet 1, Q8b): try to give a good bound on the gcd's between any two of those numbers; which primes can divide those gcd's?

Reading suggestions:

Apart from the library items already given on the official "Library Books" link via the web page and the official module page of the course, there are further useful books and links: perhaps the text which the course follows most closely is
• William Stein Elementary Number Theory from Springer.
This book is one of the Free Number Theory Online Library where you can find plenty of other interesting sources. William Stein also has a nice set of course notes from 2001.
• One of the classics is the book by Hardy and Wright (Introduction to the Theory of Numbers), which is also very good for self-study, and
• another highly recommended one with exactly the same title is by Niven and Zuckerman (and Montgomery in the newest edition).

  One of the most eminent number theorists in the last century was Andre Weil who has written one very nice introductory text

• Andre Weil Number Theory for Beginners Springer.

Furthermore, here you can find a large library of links (some are already outdated, alas) to online notes (some of them in French, German, Dutch or even Greek!), the more elementary of which cover quite similar number theoretic ground as the lectures. Not each source deals with cryptographic topics, though.

For some of the computations in the course, a computer--together with some suitable number theory software packages--will be almost indispensable. There are good software packages available, apart from Maple which you presumably have a license for, anyway, there is a rather convenient free one GP-PARI and an even more powerful but also more complex one called SAGE. It is intended to include examples for either package during the course, and it is strongly recommended that you familiarise yourself with at least one of them.