In which we conclude our study of methods of factorising large numbers, and, indeed, the course.
- Lemma 76: Let be a convergent to . Then , and moreover we have . (The angle bracket notation is the same as that introduced in Lecture 7). We proved this using our upper bound on , which in turn we proved in Lecture 19.
- Description of the continued-fraction method, which is really a variant of the factor-base method that we saw last time, using Lemma 76 as a crucial ingredient.
- Description of Pollard’s method.
Koblitz (A Course in Number Theory and Cryptography) and Davenport (The Higher Arithmetic) both discuss these methods, together with other variants. Right at the end, I mentioned Shor’s algorithm for factorisation using a quantum computer; Scott Aaronson has written a lovely non-technical description on his blog, and he includes links to a number of sources of more information.
I hope that some of you may be inspired to read in more depth about the ideas of this course, and about other aspects of number theory. Of course, there are many number theory books and many websites where you can do this, so I shan’t try to list them (but please do share your favourites in the comments below).
I’ll just mention one book, The Princeton Companion to Mathematics, edited by Tim Gowers (with associate editors June Barrow-Green and Imre Leader). This has short sections on various important concepts in pure mathematics, including several from number theory (such as elliptic curves, the Euclidean algorithm and continued fractions, the ideal class group, L-functions, modular arithmetic, number fields, the Riemann zeta function and many more). Perhaps even more interestingly, it has slightly longer articles (10–20 pages) on branches of mathematics, written by leading mathematicians in those areas. So there’s “Algebraic Numbers” by Barry Mazur, “Analytic Number Theory” by Andrew Granville, “Computational Number Theory” by Carl Pomerance, “Arithmetic Geometry” by Jordan S. Ellenberg, and many more (they aren’t all about number theory!). And then there are short pieces about particular theorems and problems, such as the ABC conjecture, the Birch–Swinnerton-Dyer conjecture, Fermat’s last theorem, the Prime Number Theorem and the Riemann Hypothesis, Problems and Results in Additive Number Theory, and so on. If you want a broader picture of mathematics and how the ideas from your various lecture courses are used, and if you want to know what current research mathematicians in the area are thinking about, this would be a great place to start reading. Perhaps your college library has a copy?
Preparation for Lectu… oh, this is the end of the course!
I plan to write about some of the topics from this course in more detail over the next few months (in the style of the `Theorem’ posts on this blog), so you might want to keep an eye out for them. And of course the comment facility is still there for asking questions. I hope that this course has inspired you to find out more about Number Theory!