Number Theory: Lecture 24

In which we conclude our study of methods of factorising large numbers, and, indeed, the course.

  • Lemma 76: Let \frac{p_n}{q_n} be a convergent for \sqrt{N}.  Then \langle p_n^2 \rangle = p_n^2 - q_n^2 N, and moreover we have |\langle p_n^2 \rangle| \leq 2 \sqrt{N}.  We proved this using the bound |p_n - q_n \sqrt{N}| \leq \frac{1}{q_{n+1}} from Lemma 62.
  • Description of the continued fraction method, a version of the factor base method.
  • Description of Pollard’s p-1 method.

Understanding today’s lecture

You could pick some large numbers N and try running the continued fraction method and Pollard’s p-1 method on them.

Further reading

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, which I mentioned briefly before, 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 might 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, or look back over the posts that are already there.  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!


One Response to “Number Theory: Lecture 24”

  1. m usman Says:

    i got a question regarding the relationship between the order and the index of a subgroup of a finite group. i used to go to ask nrich for such questions but it is not accessible anymore so can u tell where can i go for my question?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: