Extending Lenstra's Primality Test to CM elliptic curves and a new quasi-quadratic Las Vegas algorithm for primality

2022/12/08 by T. G. Nageshwar Rao, Rao, Tejas
Computer Science · #11G07 (Secondary) #11Y11 (Primary) 11G15 #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2212.04463

openalex publication_date 2022/12/08 · openalex created_date 2022/12/22 · openalex updated_date 2026/07/28

Abstract

For an elliptic curve with CM by K defined over its Hilbert class field, E/H, we extend Lenstra's finite fields test to generators of norms of certain ideals in O_H, yielding a sufficient \widetildeO(log³ N) primality test and partially answering an open question of Lemmermeyer in the case of CM elliptic curves. Letting ι,γ, b∈ O_K, (ι) prime, and b a primitive k-th root of unity modulo (ι)ⁿ we specialize this test to rational integers of the form N_K/ℚ(γιⁿ+b) with the norm of γ small, giving a Las Vegas test for primality with average runtime \widetildeO(log² N), that further certifies primality of such integers in \widetildeO(log² N) for nearly all choices of input parameters. The integers tested were not previously amenable to quasi-quadratic heuristic primality certification.

Related

• Primality tests for 2^kn-1 using elliptic curves
• Primality tests for Fermat numbers and 2^(2k+1)±2^(k+1)+1
• Four primality testing algorithms
• Constructing elliptic curves with a known number of points over a prime field
• Dual Elliptic Primes and Applications to Cyclotomy Primality Proving