pyca/ed25519 — pull request #7 by swenson (2013-10-05 04:33:27+00:00)
Title: Use extended Euclidean algorithm for modular inverse

This roughly doubles the speed of the ed25519 implementation in Python.

The flaw in the previous code is that is assumes squaring is faster than it is in Python. Python uses the naive schoolbook multiplication algorithm, which is quadratic, so we are better off just using the standard extended Euclidean algorithm for computing modular inverses.

Before:

Time generate
2.8231959343

Time create signature
5.24891996384

Time verify signature
7.75262784958

After:

Time generate
1.58998298645

Time create signature
3.2284090519

Time verify signature
4.52029514313