A framework for deterministic primality proving using elliptic curves with complex multiplication

Alexander Abatzoglou, Alice Silverberg, Andrew V. Sutherland, Angela Wong

Published 2014-04-01, updated 2014-10-11Version 3

We provide a framework for using elliptic curves with complex multiplication to determine the primality or compositeness of integers that lie in special sequences, in deterministic quasi-quadratic time. We use this to find large primes, including the largest prime currently known whose primality cannot feasibly be proved using classical methods.