## Number Theory: Lecture 22

In which we meet two more types of pseudoprime, and their corresponding primality tests.

• Definition of an Euler pseudoprime.
• Lemma 72: If there is a base $b$ to which $n$ is not an Euler pseudoprime, then $n$ is an Euler pseudoprime to at most half of all possible bases.  Our proof followed the approach in Lemmas 70 and 71.
• 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 used Lemma 72, so all we had to do was to show that there was some base to which $n$ was not an Euler pseudoprime.  We did this by splitting into two cases, one where $n$ is divisible by the square of a prime and one where $n$ is a product of distinct primes.
• Description of the Solovay-Strassen primality test.
• Definition of a strong pseudoprime.
• 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 omitted the proof.
• Theorem 75: If $n$ is an odd composite natural number, then $n$ is a strong pseudoprime to at most one quarter of all possible bases.  We omitted the proof.
• Description of the Miller-Rabin primality test.

#### Understanding today’s lecture

You could look for some composite numbers that are Euler pseudoprimes or strong pseudoprimes to various bases.  Perhaps you can set yourself particular challenges (“Can I find a number that is an Euler pseudoprime to the base 2?”, for example).

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.  Andrew Granville wrote an article about it for a general audience (it has amusing cartoons and everything).

#### 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?