Andre Nies: Prime numbers, factorisation, and algorithms

Abstract

Euclid in around  300 BC proved that the sequence of prime numbers is infinite. This sequence starts 2,3,5,7,11, 13, …; the largest currently known prime number  is  obtained by raising 2 to the power of 82589933 and subtracting 1. Each number is a unique product of prime numbers; so the prime numbers  can be seen as the building blocks for all natural numbers. 

The first part of the talk gives an overview of prime numbers, including a fairly recent result of Green and Tao on arithmetic progressions,  and close calls to the Goldbach conjecture due to Wang, Helfgott, and others. 

The second part focusses on computation: how to recognise via an efficient (i.e., polynomial time) algorithm whether a number is prime, and how to use a hypothetical quantum computer to obtain the prime factorisation of a number in polynomial time. The relevance to cryptography will be discussed as well.

Speaker Bio

PhD 1992, Heidelberg

University of Chicago, 1995-2001

University of Auckland, 2002-

2010 ICM speaker in special session

2020 Humboldt research award