Author: Christian SiebertChristian Siebert
Date: May 13, 2008 09:33
Hi all,
as far as I can see, the extended Euclidean algorithm seems to be the
most common algorithm for computing the modular multiplicative inverse
(used in GMP, LibTomMath, ...). The only alternative I've seen so far
utilizes Euler's totient function and direct modular exponentiation.
However, this algorithm is generally much slower (O(n^3) VS O(n^2)).
Are there any other known algorithms? I ask because I've discovered a
plain method which is even easier (to understand as well as to
implement) than Euclid's algorithm (maybe some simplified version of
the eEa?). It's so simple that I wouldn't be surprised if this is
something that is already known ...
Regards,
Christian
|