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, ...). [...]
Are there any other known algorithms?

Christian Siebert  wrote:
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, ...). [...]
Are there any other known algorithms?

If I recall correctly, I _think_ you can use any extended-gcd algorithm
(e.g., the extended version of the binary gcd algorithm), though this is
a vague memory, I could be misremembering, and I really don't know this
area.

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 ...

In http://www-lipn.univ-paris13.fr/~sedjelmaci/abstract27.pdf "The
Accelerated Euclidean Algorithm", Sidi Mohamed Sedjelmaci gives an
algorithm said to have O(n (log n)^2 log log n) complexity, for n-bit
inputs. (Eg: if input = 2^256-7, then n=256 and (log n)^2 log log n is

equal to 256*8*8*3.)
....

Christian Siebert wrote:
... the extended Euclidean algorithm seems to be the most common
algorithm for computing the modular multiplicative inverse

If I recall correctly, I _think_ you can use any extended-gcd
algorithm (e.g., the extended version of the binary gcd algorithm)

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 ...

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)).
This is normally reads O((log n)^3) and O((log 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 ...

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 ...

However, this algorithm is generally much slower (O(n^3) VS O(n^2)).

This is normally reads O((log n)^3) and O((log n)^2.
yes, I'm sorry (it was just for the sake of brevity, i.e. 'n=log

It will be much easier for the discussion if you give some more info
about your method.
I totally agree - however, it's not sooo simple once you have a

- Is it "only" easier to implement and prove? Or is it more efficient
than the gcd algorithms?
I haven't checked this issue so far. I'd say: From a theoretical point

- Is it suitable for multiple precision?
of course (already implemented/tested using GMP)

How does it scale? How does it compare to fast recursive GCD schemes?
TODO

- Is it for general moduli?
yes (at least for all 'm > 1'; current implementation returns the

A comment to you second post: If the modulus m is odd you need not
calculate "both inverses", see e.g. HAC 14.64.
thanks - I already noticed that Tom also has a fast inverse function

Perhaps you rediscovered the recursive modular inversion algorithm that
arises immediately from the Chinese Remainder Algorithm (CRT) [...]
That is great! However, for my method you do not even need to know the

On Tue, 13 May 2008 09:33:22 -0700 (PDT), Christian Siebert

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)).

This is normally reads O((log n)^3) and O((log n)^2.

- Is it "only" easier to implement and prove? Or is it more efficient
than the gcd algorithms?

I haven't checked this issue so far. I'd say: From a theoretical point
of view, it should be equivalent to a gcd algorithm. From a practical
point of view, it's simplicity might allow some improvements over the
hidden constant within the O-notation. Btw: can anyone of you give
some suggestions for a fair benchmark