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

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 − t² = Δf², 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.