**MSC:**- 11Y11
- 13B05

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.