Tool to compute the modular inverse of a number. The modular multiplicative inverse of an integer N modulo m is an integer n such as the inverse of N modulo m equals n.

Modular Multiplicative Inverse - dCode

Tag(s) : Arithmetics

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!

A suggestion ? a feedback ? a bug ? an idea ? *Write to dCode*!

Tool to compute the modular inverse of a number. The modular multiplicative inverse of an integer N modulo m is an integer n such as the inverse of N modulo m equals n.

The value of the **modular inverse** of $ a $ by the modulo $ n $ is the value $ a ^ {- 1} $ such that $ a a ^ {- 1} = 1 \pmod n $

It is common to note this **modular inverse** $ u $ and to use these equations $$ u \equiv a^{-1} \pmod n \\ a u \equiv 1 \pmod n $$

If a **modular inverse** exists then it is unique.

To calculate the value of the modulo inverse, use the extended euclidean algorithm which find solutions to the Bezout identity $ au + bv = \text{G.C.D.}(a, b) $. Here, the gcd value is known, it is 1 : $ \text{G.C.D.}(a, b) = 1 $, thus, only the value of $ u $ is needed.

__Example:__ $ 3^-1 \equiv 4 \mod 11 $ because $ 4 \times 3 = 12 $ and $ 12 \equiv 1 \mod 11 $

dCode uses the Extended Euclidean algorithm for its inverse modulo N calculator and arbitrary precision functions to get results with big integers.

Use the Bezout identity, also available on dCode.

The keyword invmod is the abbreviation of inverse modular.

A multiplicative inverse is the other name of a **modular inverse**.

dCode retains ownership of the online 'Modular Multiplicative Inverse' tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (PHP, Java, C#, Python, Javascript, Matlab, etc.) no data, script or API access will be for free, same for Modular Multiplicative Inverse download for offline use on PC, tablet, iPhone or Android !

Please, check our community Discord for help requests!

invmod,inverse,modular,modulo,mod,euclide,gcd,bezout,calculator,multiplicative

Source : https://www.dcode.fr/modular-inverse

© 2020 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲