
Software
We have Sage implementations of Elligator for automated verification,
but we don't have serious performanceoriented implementations yet.
This page reports preliminary performance estimates.
Here are some figures from
the Ed25519 paper
and eBATS
for a highsecurity curve (Curve25519) on an Intel Westmere CPU:
 Full scalar multiplication takes 226872 cycles.
 Fixedbasepoint scalar multiplication takes only 80352 cycles.
 Standard point decompression takes only 44000 cycles.
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 256bit inputs
despite the overhead of being a generalpurpose 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.
Version:
This is version 2013.08.29 of the software.html web page.
