Elliptic Curves of Fibonacci order over ${\mathbb{F}}_p$

We will describe an algorithm to construct an elliptic curve $E_{f_q}$ over some prime field ${\mathbb{F}}_p$ such that such that $|E_{f_q}($\mathbb{F}$_p)| = f_q$,where$f_q$isaprobableFibonacciprimeforsomeprimeindex$q$. The algorithm is a variant of the efficient CM-construction by Br$\ddot{o}$ker and Stevenhagen, which is well suited for Fibonacci primes due to their arithmetic properties. The time complexity of our algorithm is expected to be lower than $\tilde{O}({\log }^3(f_q))$. The construction process is a series of algorithms, where each is a test for primality.