2017/10/16 by Campbell, Rosina, Van Huynh, Duc, Melton, Tyler +1
#FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1710.05687
We will describe an algorithm to construct an elliptic curve Efq over some prime field \mathbbFp such that such that |Efq(\mathbbFp)| = fq, where fq is a probable Fibonacci prime for some prime index q. The algorithm is a variant of the efficient CM-construction by Broker 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 \widetildeO(log3(fq)). The construction process is a series of algorithms, where each is a test for primality.