Category Archives: Maths

Polynomial factorisation over finite fields, part 0: Overview

Another cool problem in computational number theory is how to factor a polynomial with coefficients in a finite field. Recall that for a field $K$, the ring $K[X]$ of polynomials in one indeterminate with coefficients in $K$ is a unique factorisation domain (UFD), which means that every polynomial of $K[X]$ can be factored as a product of irreducible polynomials and that this factorisation is unique up to order and unit factors. We are interested in finding a complete factorisation of a polynomial when $K$ is a finite field. Like primality testing, this involves several algorithms which must be run successively, so in this first post I will give an overview of each one, and I will describe them in detail in later posts.

Continue reading

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:

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading

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.

Continue reading

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:

1 – R vs. Q and number fields
2 – Rings
3 – Unique factorisation
4 – Cyclotomic fields

1 – $\mathbf{R}$ vs. $\mathbf{Q}$ and number fields

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

In the introductory post of my series on field theory, I remarked that $\mathbf{Q}$ is a lot more complicated than $\mathbf{R}$ from a field-theoretic standpoint. The reader who has worked through the questions at the end of each post will probably already have some idea of what was meant by that. This first post on algebraic number theory will elaborate on this, and introduc number fields, which are the main objects of study in this discipline.

Continue reading