Mihailescu Preda
Dual Elliptic Primes and applications to cyclotomic primality proving
Preprint series: Mathematica Gottingensis
MSC:
11Y11
13B05
Abstract: Two rational primes $p, q$ are called {\em dual elliptic} if there is
an elliptic curve $E \mod p$ with $q$ points. They were introduced as
an interesting means for combining the strengths of the elliptic curve
and cyclotomy primality proving algorithms. By extending to elliptic
curves some notions of galois theory of rings which were introduced in
the cyclotomy primality tests, one obtains a new algorithm which
generates certificates that can be verified in quadratic
time. Provided some tables of Jacobi sums are precomputed, the test
itself requires cubic time.

Keywords: elliptic curves, primality proofs, dual elliptic primes