Scribd
Upload
8 views4 pages

Python Modular Inverse Functions

The document contains Python code for performing modular arithmetic operations, including addition, subtraction, multiplication, and finding modular inverses using both direct and extended Euclidean algorithms. It also includes functions to compute the GCD of two numbers and Euler's Totient Function for a given integer. Each section provides example usage for user input and output display.

Uploaded by

incognitotab700
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
8 views4 pages

Python Modular Inverse Functions

The document contains Python code for performing modular arithmetic operations, including addition, subtraction, multiplication, and finding modular inverses using both direct and extended Euclidean algorithms. It also includes functions to compute the GCD of two numbers and Euler's Totient Function for a given integer. Each section provides example usage for user input and output display.

Uploaded by

incognitotab700
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1. Perform modular addition, subtraction, multiplication and inverse (mod 17).

# Define modulus

mod = 17

# Modular Addition

def mod_add(a, b):

return (a + b) % mod

# Modular Subtraction

def mod_sub(a, b):

return (a - b) % mod

# Modular Multiplication

def mod_mul(a, b):

return (a * b) % mod

# Modular Inverse

def mod_inv(a):

try:

return pow(a, -1, mod) # Python 3.8+ syntax

except ValueError:

return None # No inverse exists if a and mod are not coprime

# Example usage

a=7

b=5

print(f"({a} + {b}) mod {mod} = {mod_add(a, b)}")

print(f"({a} - {b}) mod {mod} = {mod_sub(a, b)}")


print(f"({a} * {b}) mod {mod} = {mod_mul(a, b)}")

inv_a = mod_inv(a)

if inv_a is not None:

print(f"Inverse of {a} mod {mod} = {inv_a}")

else:

print(f"{a} has no inverse mod {mod}")

2. WAP to find GCD of two numbers using Euclidian algorithm.

def gcd(a, b):

while b != 0:

a, b = b, a % b

return a

# Example usage

x = int(input("Enter first number: "))

y = int(input("Enter second number: "))

print(f"GCD of {x} and {y} is {gcd(x, y)}")

[Link] Euler’s Totient Function φ (n) for a given n.

def euler_totient(n):

result = n

p=2
while p * p <= n:

if n % p == 0:

# If p divides n, then subtract multiples of p

while n % p == 0:

n //= p

result -= result // p

p += 1

# If n is greater than 1, it means n is prime

if n > 1:

result -= result // n

return result

# Input from user

num = int(input("Enter a positive integer n: "))

# Compute and display the Euler's Totient

print(f"Euler's Totient φ({num}) = {euler_totient(num)}")

4. Write a program to print Multiplication inverse of a number using extended Euclidean algorithm.

def extended_gcd(a, b):

"""

Returns a tuple (gcd, x, y) such that: a*x + b*y = gcd

"""

if b == 0:
return a, 1, 0

else:

gcd, x1, y1 = extended_gcd(b, a % b)

x = y1

y = x1 - (a // b) * y1

return gcd, x, y

def mod_inverse(a, m):

gcd, x, _ = extended_gcd(a, m)

if gcd != 1:

return None # Inverse doesn't exist if a and m are not coprime

else:

return x % m

# Example usage

a = int(input("Enter number: "))

m = int(input("Enter modulus: "))

inverse = mod_inverse(a, m)

if inverse is not None:

print(f"Multiplicative inverse of {a} mod {m} is: {inverse}")

else:

print(f"{a} has no multiplicative inverse mod {m}")

You might also like