Otimizing Elligator 1 on Curve1174
Published:
In the context of the Advanced Systems Lab, my group and I created an optimized implementation of Bernstein’s Elligator 1 mapping. Some of our major optimizations, including exponentiation with constant exponents close to a power of two, can be applied to other problems: they are often useful in modular inversion with prime modulus or finding the quadratic residue. Furthermore, we provide conceptual implementations of Elligator 1 in C, Python, and Sage. The C implementation features a custom Big Integer library, which we optimized for Elligator 1.