We have Sage implementations of Elligator for automated verification,
but we don't have serious performance-oriented implementations yet.
This page reports preliminary performance estimates.
Here are some figures from
the Ed25519 paper
for a high-security curve (Curve25519) on an Intel Westmere CPU:
The basic bottleneck for Elligator
is exactly the same sqrt computation used for standard point decompression.
There are also a few chi computations,
but libgmp computes chi (mpz_jacobi)
in only 9000 cycles for 256-bit inputs
despite the overhead of being a general-purpose library.
The loop in the protocols in Section 2 of the paper is repeated twice on average,
but each iteration takes only 80352 cycles plus one chi computation.
- Full scalar multiplication takes 226872 cycles.
- Fixed-base-point scalar multiplication takes only 80352 cycles.
- Standard point decompression takes only 44000 cycles.
This is version 2013.08.29 of the software.html web page.