Number Theory: Lecture 22

In which we continue our examination of various sorts of pseudoprime.

  • Lemma 72: If n is not an Euler pseudoprime to some base b, then for at least half of all bases we find that n is not an Euler pseudoprime.  This was analogous to Proposition 71 last time, and the proof was almost identical.
  • Proposition 73: Let n be an odd composite natural number.  Then n is an Euler pseudoprime to at most half of all bases.  (So there are not numbers analogous to Carmichael numbers.)  We showed that there is some base b to which n is not an Euler pseudoprime, and then used Lemma 72.  We split into two cases, depending on whether n is divisible by the square of a prime or not.
  • Description of the Solovay-Strassen primality test, a probabilistic primality test that relies on Proposition 73 for its usefulness.
  • Definition of a strong pseudoprime to the base b.
  • Proposition 74: Let n be an odd composite natural number.  If n is a strong pseudoprime to the base b, then it is also an Euler pseudoprime to the base b.  We did not prove this in the lecture.
  • Theorem 75: If n is an odd composite natural number, then n is a strong pseudoprime to the base b for at most one quarter of all possible bases.  We did not prove this either.
  • Description of the Miller-Rabin primality test, another probabilistic primality test.
  • We mentioned the Agrawal-Kayal-Saxena primality test, without going into any details.  See below for a reference.

I gave out the fourth (and final) examples sheet, which is now also available on the course page.  Here are a couple of comments on that examples sheet.

Q5(ii).  You are, of course, supposed to incorporate the condition from part (i) into this statement.  I omitted it to avoid making the question even longer, but this seems to have caused some confusion.  My apologies to those of you who were unclear about this.

Q15.  There is no harm in trying the question as written on the sheet, but I meant to put N = 53467 — the question is more interesting that way!

Further reading

Koblitz (A Course in Number Theory and Cryptography) and Davenport (The Higher Arithmetic) both have material on pseudoprimes and primality testing.  Terry Tao has a blog post about the AKS primality test, with various links to further reading.

Preparation for Lecture 23

Next time we’ll be thinking about factorisation.  Given a large integer N, we’d like to find a non-trivial factor.  Why might it help to find two squares that are congruent modulo N: that is, r and s such that r^2 \equiv s^2 \pmod{N}?  And can we always find such squares?


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: