Project Description
There are various use cases in cryptography that require the use of an elliptic curve defined over a finite field of cryptographic size whose number of rational points is known: For example, some zero-knowledge interactive proofs require them, and new post-quantum cryptographic schemes require the construction of a supersingular elliptic curve whose endomorphism ring is unknown. Unfortunately, the state of the art in this field is a guess-and-check (as in, guess an elliptic curve, and then check how many points it has) algorithm whose asymptotic complexity is quartic in the size of the underlying finite field.
This project is a first step towards developing a completely different algorithm which we believe will run in time linear in the size of the underlying finite field. At this time we will implement an algorithm that is closely related to the one we hope to develop, as it computes the action of Hecke operators on modular forms of level 1 (instead of the forms of general level N which we will need for the application we have in mind). This will allow us to identify the parts of the code that can be parallelized, as well the parts of the code that must be written in Python to access advanced mathematical software libraries such as SageMath, and those that can be written in Cython or C++ to increase speed. This will also allow us to set some performance benchmarks to estimate the constants in the asymptotic complexity estimate, which will help us determine if this new algorithm will be faster in the range of values we are considering for this application.