An Algorithmic Construction of Finite Elliptic Curves of Order Divisible by a Large Prime

Article type: Research Article

Authors: Grześkowiak, Maciej

Affiliations: Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland. maciejg@amu.edu.pl

Note: [] The author was partially supported by the grant no. N N201 605940 from National Science Centre. Address for correspondence: Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland

Abstract: Given a square-free integer Δ < 0, we present an algorithm constructing a pair of primes p and q such that q|p + 1 − t and 4p − t2 = Δf2, where |t| ≤ 2√p for some integers f, t. Together with a CM method presented in the paper, such primes p and q are used for a construction of an elliptic curve E over a finite field $\mathbb{F}_p$ such that the order of E is divisible by a large prime. It is shown that our algorithm works in polynomial time.

Keywords: Elliptic curves over finite field, public key cryptography

DOI: 10.3233/FI-2015-1161

Journal: Fundamenta Informaticae, vol. 136, no. 4, pp. 331-343, 2015