Welcome guest
You're not logged in.
245 users online, thereof 0 logged in

Algorithm: Calculation of Inverses Modulo a Number (Python)

Calculation of Inverses Modulo a Number (Python)

Known time/storage complexity and/or correctness

Let \(a,b\in\mathbb{Z}\) be positive integers $a,b\in\mathbb Z$ with \(a\le b\) which are co-prime. The algorithm \(\operatorname{invmod}(a,b)\) calculates correctly the multiplicative inverse $a^{-1}$ in the ring of congruences $\mathbb Z_b,$ i.e. for which $$a\cdot a^{-1}\equiv 1\mod b.$$ In particular, if $b=p$ is a prime number, this is the unique inverse of $a$ modulo $b$ in the field of congruences $\mathbb Z_p.$

The algorithm requires \(\mathcal O(\log |b|)\) (worst case and average case) division operations, which corresponds to \(\mathcal O(\log^2 |b|)\) bit operations.

Short Name

$\operatorname{invmod}$

Input Parameters

$a,b\in\mathbb{Z}$, $0 < a \le b$, $a\perp b$

Output Parameters

$a^{-1}$ with $a\cdot a^{-1}\equiv 1\mod b.$

Python Code

def invmod(a, b):
    res = gcdext(a, b)
    if res[0] != 1:
        raise NotCoPrimeException(a, b)
    else:
        if res[1] < 0:
            res[1] = res[1] + (abs(res[1]) // b + 1) * b
        return res[1]


# Usage
print(invmod(16, 21))


# will output
# 4, since 16*4=1 mod 21

| | | | created: 2019-06-22 05:21:55 | modified: 2019-06-22 07:42:54 | by: bookofproofs | references: [1357], [8187]

1.Proof: (related to "Calculation of Inverses Modulo a Number (Python)")


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[8187] Blömer, J.: “Lecture Notes Algorithmen in der Zahlentheorie”, Goethe University Frankfurt, 1997

[1357] Hermann, D.: “Algorithmen Arbeitsbuch”, Addison-Wesley Publishing Company, 1992

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.