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

\textit{S. Goldwasser} and \textit{J. Kilian} [``Almost all primes can be quickly certified'', in: Proc. 18th STOC, 316--329 (1986)] propose a general primality test using elliptic curves. The Goldwasser-Kilian algorithm takes random curves until it find one with suitable cardinal. A variant due to \textit{A. O. L. Atkin} and \textit{F. Morain} [Math. Comput. 61, No. 203, 29--68 (1993; Zbl 0792.11056)] proposes to construct instead elliptic curves with cardinal preset using tools of complex multiplication (CM).NEWLINENEWLINELater on other papers presented efficient primality tests for some particular families of numbers, using elliptic curves with CM. The aim of the present paper is to provide a general framework including and extending those previous proposals.NEWLINENEWLINEThe Introduction of the paper gives a good summary of the \textit{state of the art} on the problem of primality tests with elliptic curves with CM. Section 3 gathers some theoretical results concerning elliptic curves with CM by the ring of integers of a quadratic imaginary field \(\mathbf{K}=\mathbb{Q}(\sqrt{-d})\)\, (Theorems 3.5 and 3.6) and deduces some general primality tests (Algorithms 3.8 and 3.9). Section 4 discusses the cases of \(\mathbf{K}\)\, with class number one (Theorem 4.8) and class number 2 (Theorem 4.9).NEWLINENEWLINESection 5 studies a primality test using an elliptic curve with CM by \(\mathbb{Q}(\sqrt{-2})\), ``a case not previously addresses with elliptic curves'' and finally Section 6 shows a primality test (Algorithm 6.3) using an elliptic curve with CM by \(\mathbb{Q}(\sqrt{-15})\),\, a field with class number two.