2007/09/26 by Preda Mihăilescu, Preda Mihailescu, Mihailescu, Preda · 1 citation
Computer Science · Mathematics · #11Y11 #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #Rings and Algebras (math.RA) #math.NT #math.RA #msc:11Y11
paper · pdf · doi:10.48550/arxiv.0709.4113
arxiv created 2007/09/26 · openalex publication_date 2007/09/26 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two rational primes p, q are called 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 used in the cyclotomy primality tests, one obtains a new algorithm which has heuristic cubic run time and generates certificates that can be verified in quadratic time. After the break through of Agrawal, Kayal and Saxena has settled the complexity theoretical problem of primality testing, some interest remains for the practical aspect of state of the art implementable proving algorithms.