Modular Mulitplicative Inverse¶
source geeksforgeeks
Method¶
- Naive Method, O(m)
- Extended Euler’s GCD algorithm, O(Log m) [Works when a and m are coprime]
- Fermat’s Little theorem, O(Log m) [Works when ‘m’ is prime]
Method 1¶
Time Complexity: O(m)
def modInverse(a, m):
for x in range(1, m):
if (((a%m) * (x%m)) % m == 1):
return x
return -1
a = 3
m = 11
print(modInverse(a, m))
Method 2¶
(Works when m and a are coprime)
Time Complexity: O(Log m)
def modInverse(a, m):
m0 = m
y = 0
x = 1
if (m == 1):
return 0
while (a > 1):
# q is quotient
q = a // m
t = m
# m is remainder now, process
# same as Euclid's algo
m = a % m
a = t
t = y
# Update x and y
y = x - q * y
x = t
# Make x positive
if (x < 0):
x = x + m0
return x
a = 3
m = 11
print("Modular multiplicative inverse is", modInverse(a, m))
Bentuk sederhana
def modInv(a, m, x1, y1):
if a <= 1:
if y1 < 0:
y1 += x1
return y1
x=y1-(a//m)*x1
y=x1
return modInv(m, a%m, x, y)
a, m = 13, 107
x, y = 0, 1
print(modInv(a, m, x, y))
Method 3¶
(Works when m is prime)
Time Complexity: O(Log m)
def modInverse(a, m):
g = gcd(a, m)
if (g != 1):
print("Inverse doesn't exist")
else:
# If a and m are relatively prime,
# then modulo inverse is a^(m-2) mode m
print("Modular multiplicative inverse is ",
power(a, m - 2, m))
# To compute x^y under modulo m
def power(x, y, m):
if (y == 0):
return 1
p = power(x, y // 2, m) % m
p = (p * p) % m
if(y % 2 == 0):
return p
else:
return ((x * p) % m)
# Function to return gcd of a and b
def gcd(a, b):
if (a == 0):
return b
return gcd(b % a, a)
# Driver Code
a = 3
m = 11
# Function call
modInverse(a, m)
Bentuk sederhana