Speaker:Prof. Tim Gowers, FRS (DPMMS)
Venue: Old Combination Room, Trinity College
Time: 09/10/2006 20:30, drinks from 20:15

The talk is available.

Suppose you are given a number n and asked to determine whether it is prime. One time-honoured method is to see whether it is a multiple of 2, then of 3, then of 5, and so on, all the way up to the square root of n. This works fine for a number such as 147, but is not very practical if n has a hundred digits, say. A related problem, of great importance in cryptography, is to factorize a large integer that somebody gives you. Again, it can be done by simply searching through all the primes until you stumble on a factor, but again this takes far too long if the number is large. It is not at all obvious how one might go about finding faster approaches to these computational tasks. However, some very clever techniques have been discovered, and some of these are not especially hard to understand. This talk will present a few of them.