# Primality testing, part 2: The Pocklington-Lehmer primality test

(Continues this post.)

So we have this integer $n$, and we would like to know whether it is prime or not. We have used the Rabin-Miller compositeness test on it a couple times and it has always turned negative, so the probability that $n$ is not prime is excruciatingly small. Still, we have not proved that $n$ is prime; in order to do that, we need a real primality test. Basically, we are looking for a converse to Fermat’s theorem. Such a converse was found by Pocklington and improved by Lehmer. Essentially, it is based on the fact that an integer $a$ of multiplicative order $n-1$ modulo $n$ (i.e., such that $a^{n-1} \equiv 1 \pmod n$ and $a^e \not \equiv 1 \pmod n$ for all positive $e < n-1$) exists if and only if $n$ is prime. More precisely:

# Primality testing, part 1: Compositeness tests, Fermat and Rabin-Miller

How to check that a given integer is prime? Of course we can do the naive method of trial division up to $\lceil \sqrt{n} \rceil$, but this becomes impossible in practice if $n$ is at all large, so we need something better. (Note that trial division is actually used in practice, up to a point, in order to quickly conclude that a given integer is composite if it has some small prime factors.)

A common strategy is to first perform a compositeness test, which can either say with certainty that the given integer is composite, or say that it is prime with high but not 100% probability. Then, once we are, in the words of Cohen, “morally certain” that our integer is prime, we do a real primality test in order to prove it. The reason for this strategy is that in general compositeness tests are easy but primality tests are hard, so it makes sense to first acquire a high degree of certainty that a number is prime before doing a primality test. In this post we will see two compositeness tests, the Fermat test, which is based on Fermat’s little theorem, and the Rabin-Miller test, and experiment with them using Sage (for a change). In a next post we will see primality tests.

# 6 – Algebraic integers, unique factorisation, and Fermat’s last theorem

(This is part of my series on algebraic number theory.)

The foundations of what is now algebraic number theory were devised in the late 19th century in various attempts to prove Fermat’s last theorem, which states that the equation
$x^n+y^n = z^n$
has no solution in positive integers when $n > 2$. This post will give the first part of an attempted proof by Lamé in 1847, using unique factorisation in certain subrings of number fields.

# 5 – Computing in number fields

(This is something of a computational aside in my series on algebraic number theory.)

Recall that a number field is a field of the form $\mathbf{Q}(\omega)$, where $\omega$ is a complex number which is algebraic over $\mathbf{Q}$ (that is, is a root of some polynomial in rational coefficients). Then the elements of $\mathbf{Q}(\omega)$ are of the form
$a_0 + a_1\omega + a_2\omega^2 + \dots + a_{n-1}\omega^{n-1},$
where $n$ is the degree of $\omega$ over $\mathbf{Q}$ (that is, the degree of a monic, irreducible polynomial in rational coefficients which has $\omega$ as a root).

What this means is that an element of a number field can essentially be viewed as a polynomial in rational coefficients, and in turn this means that we can easily perform the operations of addition and multiplication in any number field (indeed, in any field extension, provided we can easily compute in the base field). This post will demonstrate how this is done, both by hand when the number field is manageable, and with a computer using PARI/GP. The standard reference for computational matters in number fields (and many others) is the book by Cohen.

# 4 – Cyclotomic fields

(This is part of my series on algebraic number theory.)

In this post we present a special class of number fields called cyclotomic fields which are of particular interest. Very thick volumes have been written on cyclotomic fields alone, for instance by Lang or, on a more introductory level, by Washington.

# 3 – Unique factorisation

(This is part of my series on algebraic number theory.)

Since number theory is ultimately concerned with problems in the ring of integers $\mathbf{Z}$, we try to find rings which share as many properties with $\mathbf{Z}$ as possible. In the previous post we have seen commutative rings with unity, which share two key properties of $\mathbf{Z}$. In this post we present two additional properties of $\mathbf{Z}$ which are shared by the rings we will be ultimately interested in. Of course, the title of this post gives a hint of what we are after. ;) In this post and all the subsequent ones, when we speak of a ring, we mean a commutative ring with unity.

# 2 – Rings

(This is part of my series on algebraic number theory.)

We have seen that most of the number systems we are familiar with (the rational, real, and complex numbers) are fields. There is one notable exception: the set $\mathbf{Z}$ of integers. Indeed, if you try to tick all the boxes in the definition of a field, you see that $\mathbf{Z}$ does not fulfill all the requirements. It comes close, however: the only requirement it fails to fulfill is the existence of multiplicative inverses for all its elements. Perhaps then it might be worthwhile to relax our requirements a little and consider sets which have the same properties as $\mathbf{Z}$. This post deals with such sets, called rings.

# Algebraic number theory

This is a series of posts on algebraic number theory which builds upon my previous series on field theory. The goals are mostly the same: to give the interested reader with only a modest background in mathematics a first “feel” of the subject, and perhaps to motivate further study. I have tried to also keep the same style of exposition, but the pace will be somewhat faster, and might be difficult to follow for the reader who has merely read my previous series and not otherwise done a lot of work with the basic objects of algebra (groups, rings, fields, polynomials).

For the (relative) beginner wishing to study algebraic number theory I warmly recommend Marcus’s book (and indeed much of what I will write in this series will be based on it). At the beginning, it requires only a very modest background in abstract algebra (having studied everything in Fraleigh’s book will more than suffice), and the level rises progressively, which makes it possible to study it in parallel with a more advanced course in abstract algebra.

The posts are as follows:

# Linux smart card authentication – TrueCrypt

(This is part of my howto on smart card authentication in Linux.)

If you are already familiar with using keyfiles in TrueCrypt, using a smart card works the same way, except the file will be stored on your card, not on the disk.

# Linux smart card authentication – OpenSSH

(This is part of my howto on smart card authentication in Linux.)

You can use the private key stored on your smart card to authenticate on a remote OpenSSH server using key-based authentication. If you are not familiar with OpenSSH key-based authentication, the Ubuntu Server Guide has a page about it.