Prime numbers, factorization, and algorithms

Unraveling Prime Numbers: From Euclid to Quantum Algorithms

  • Date: 26 SEPTEMBER 2023  from 17:30 to 19:00

  • Event location: Institute of Advanced Studies - Sala Rossa, Palazzo Marchesini, Via Marsala, 26 - Bologna - In presence and online event

  • Type: Lectures

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 some fairly recent results on arithmetic progressions and close calls to the Goldbach conjecture. 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 factorization of a number in polynomial time. The relevance to cryptography will be discussed as well. 


ISA Visiting Fellow - André Nies

The University Of Auckland, New Zealand

Visit Prof. Nies' web page

PhD students and researchers who are interested may request an attendance certificate. 
The delivery of the attendance certificate requires the attendance of at least 70% of the lecture.