Constructing elliptic curves in almost polynomial time

Reinier Broker, Peter Stevenhagen

We present an algorithm that, on input of a positive integer N together with its prime factorization, constructs a finite field F and an elliptic curve E over F for which E(F) has…