Modulus Multiplicative Inverse

• https://colab.research.google.com/drive/1FO5aWy1gRP5LLVYgPbVXLjZeymBu83ce?usp=sharing

Code

Recursive

def modularInverseRecursive(num, mod):
    if num == 1: return 1
    return (mod - mod // num) * modularInverse(mod % num, mod) % mod

Iterative

def modularInverseIterative(num, mod):
    for i in range(1, mod):
        if ((num % mod) * (i % mod)) % mod == 1: return i
    return -1

References

1. https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/