Note that there is also Maple code for elliptic curves available under the name Apecs.

Contents:

New: All lecture notes combined into one pdf

Lecture 1 (Th 7.10.): Overview (draft text)

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

Problems Class/Lecture (Tu 12.10.) and Lecture 3 (Th 14.10.): Greatest common divisor, division algorithm, Euclidean algorithm.

Lecture 4 (Tu 19.10.) Fundamental Theorem of Arithmetic. Are there infinitely many primes?

Lecture 5 (Th 21.10.) (Towards the) Prime Number Theorem.

Lecture 6 (Tu 26.10.) The Prime Number Theorem and primes in arithmetic progression.

Lecture 7 (Th 28.10.) Congruences, towards Fermat's Little Theorem.

Lecture 8 (Tu 2.11.) Fermat's Little Theorem, linear congruences, Euler-Fermat, Euler phi function.

Lecture 9 (Th 4.11.) Wilson's Theorem, Chinese Remainder Theorem.

Lecture 10 (Tu 9.11.) Chinese Remainder Theorem, Applications.

Lecture 11 (Th 11.11.) Modular exponentiation, towards public key cryptography.

Lecture 12 (Tu 16.11.) Diffie-Hellman key exchange, computing k-th roots modulo m, trapdoor function.

Lecture 13 (Th 18.11.) Computing k-th roots modulo m (algorithm), RSA.

Lecture 14 (Tu 23.11.) Attacking/cracking RSA. Factorization methods.

Lecture 15 (Th 25.11.) Factoring with high probability. Towards primitive roots modulo a prime.

Lecture 16 (Tu 30.11.) Primitive roots modulo a prime. The discrete logarithm problem.

Lecture 17 (Th 2.12.) The discrete logarithm problem. Index calculus.

Lecture 18 (Tu 7.12.) Quadratic Residues.

Lecture 19 (Th 9.12.) Legendre symbol, Euler criterion, (towards the) quadratic reciprocity law.

Lecture 20 (Tu 14.12.) Statement and proof of the quadratic reciprocity law. Applications.

Assignments:  Set and collected every other Tuesday.

• Hand in on 14th October:  Sheet 1: Q2c), Q4a), Q7a).  
• Hand in on 26th October:  Sheet 2: Q1a),1b), [try 1c) for extra points (may be a bit harder)] and Q5.  
• Hand in on 9th November:  Sheet 3: Q5b), 5c) [try 5a) for a challenge], and Sheet 4: Q2b), Q6.  

  [Hints: for Sheet 3, Q5c) list (and then sum) all the divisors of 2^k*p, for p a prime, by grouping them into those which are divisible by p and those which are not; for Sheet 4, Q6) first show the congruence that you obtain from squaring both sides; then recall Wilson's Theorem and pair numbers off appropriately.]  

  A typo in Q 5a): it should read $n>1$, obviously. A second typo is a missing assumption in Q6) where p is supposed to be a prime. (Both spotted by Chris Moore.)

  Yet another one in Q1c) from Sheet 4: "integers mod 100" should read "integer squares mod 100".

  Hint for Q7 from Sheet 4: think Fermat's Little Theorem.

• Hand in on 23rd November:  Sheet 5: Q1b), Q2b), Q3c), and Sheet 6 Q1a)

• Hand in on 7th December:  Sheet 6: Q3a), Q5), and Sheet 7: Q2), Q4(a). Try Q4(b) for extra points.

  A typo in Q 5a) of Sheet 6: the encryption exponent should be 19 rather than 9.

  Moreover, the modulus in the public key in 5b) is far too small. Please use the key (n,e)= (100160063,17) from the lectures instead or, better still, produce one that allows you to encode your name in full. (Both spotted by Aaron Paxton.)

  For the homework please also answer the following question for Q5a): why would an encryption exponent 9 be a bad idea for the given modulus?

• Hand in on 14th December:  Sheet 8, Q1), Q4a), Q6a)+c)

  Typo in Q1a): 3^(m/32) should read 3^(m/16) [spotted by Aaron Paxton, yet again]

Problems:

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

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.