PRIMES is in P

Abstrakt:

Att avgöra om ett givet tal är ett primtal är ett grundläggande problem som dessutom är mycket viktigt bland annat i kryptografiska tillämpningar. Nyligen visade Agarwal, Kayal och Saxena att problemet går att lösa i deterministisk polynomisk tid; tidigare fanns algoritmer som krävde probabilistisk polynomisk tid samt algoritmer som bara kunde visas fungera korrekt under antagandet att vissa, obevisade, matematiska satser är sanna.

Agarwals, Kayals och Saxenas resultat har fått stor uppmärksamhet över hela världen och är av stor teoretisk betydelse. I det här seminariet kommer vi att ge en bakgrund till problemet, beskriva dess lösning och till sist diskutera vilken betydelse resultatet har, både från ett teoretiskt och ett praktiskt perspektiv.