Simon Vestberg: ECPP primality proving

Abstract: I present and aim to describe the Goldwasser–Kilian algorithm for primality proving, which is an algorithm that make use of elliptic curves and produces a primality certificate on prime input. Subsequently, I describe Atkin–Morain’s algorithm on a surface level. This is an algorithm that uses roughly the same ideas but construct curves with the correct cardinality as to not use Schoof’s algorithm of counting points on an elliptic curve.