Suppose you have a secret you wish to transmit to $n$ people, but in such a way that all of those $n$ people must collaborate in order for the secret to be revealed. In other words, it must not be possible for even $n-1$ of those people to obtain the secret, even partially, if the $n$th person does not cooperate.

# Monthly Archives: April 2013

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

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