GILA 3: Probabilistic algorithms for primality testing

Last time, we showed that prime numbers admit succinct certificates. Given a number containing bits, one could produce a “proof” that the number is prime in polynomial in space. In other words, the language containing all primes (represented in the binary expansion, say) lies in the complexity class .

In practice, though, being in does not give a good way of solving the problem by itself; for that, we want the problem to be in . Perhaps, though, that is too strict. One relaxation is to consider classes of problems that can be solved by randomized algorithms that run in polynomial time—randomized meaning that the right output comes out with high probability, that is. This is the class : by definition, something belongs to the class if there is a polynomial-time nondeterministic Turing machine such that on any computation, at least of the computation tree leads to the right answer. So the idea of is that, to decide whether a string belongs to our language , we generate a bunch of random bits and then run a deterministic algorithm on the string together with the random bits. Most likely, if the random bits were not too bad, we will get the right answer.

In practice, people tend to believe that while . But, in any case, probabilistic algorithms may be more efficient than deterministic ones, so even if the former equality holds they are interesting.

Today, I want to describe a probabilistic algorithm for testing whether a number is prime. As before, the algorithm will rely on a little elementary number theory.

 

GILA 2: Pratt certificates for primality

A strange thing has happened to me this semester. I’ve been spending more time thinking about physics and computer science than math! Granted, most of what I have been thinking about is pretty mathematical in nature, and I’ve tried to think of it that way if not.

So today in my algorithms class we were talking a bit about primality testing. It is, of course, necessary to know in practice if a given number of, say, digits is prime, for instance to use the RSA algorithm. To do this efficiently, we want our algorithm to be polynomial in . The existence of such an algorithm (the AKS algorithm) is fairly recent, and only appeared in 2002. But before that, partial results were known.

Let us consider the language that consists of all . Integers are represented in their binary expansion (or more generally their -ary expansion where ). The AKS algorithm shows that lies in the complexity class .

It is straightforward to see that ; that is, there exist short certificates to show efficiently that a number is composite. This is easy: just take a factoring as the certificate. It was also shown in the 1970s by V. Pratt that succinct certificates for primality exist, or that . I would like to explain this result, which is of course immediate from the AKS algorithm, but which has an elegant approach of its own.

 

GILA 1: Turing machines and the halting problem

I’ve decided to bow to imaginary public pressure and do a post in a different vein, which should be accessible to anyone, and which will belong to my own GILA—for those not immersed in the know of math blog lingo, that’s generally interested lay audience—series. (OK, so I just have a new interest and need some excuse for breaking my previous promises.) So, we’re going to do a bit of theoretical computer science.

Turing machines

For theoretical computer science, we need a notion of an algorithm. One could readily agree that adding two decimal numbers via the elementary school procedure, sorting integers via mergesort, and the sieve of Eratosthenes are all algorithms. In particular, anything that can be written in a programming language should qualify as one. However, this intuitive notion needs to be made precise if one wishes to use it in a mathematical sense.

It is widely agreed (the Church-Turing thesis) that the appropriate notion of algorithm is given by Turing-computability.

First of all, we will describe what a problem is. To us, it will be represented simply as a string of characters belonging to a fixed finite alphabet . For instance, there is the problem of testing whether two integers are equal can be represented as follows one has a string over the alphabet , where the separator is used to separate the two integers. Then, the (rather trivial) problem of testing whether two integers are equal becomes a question about whether a certain string has a certain property. Or, equivalently, whether it belongs to a certain language, which is a collection of strings over a fixed alphabet. In practice, we will generally speak of languages rather than problems.

A Turing machine is a device used to simulate an algorithm. Informally, a Turing machine has the following parts: