ciphers.cryptomath_module

Cryptographic mathematics module for modular arithmetic operations.

This module provides utilities for cryptographic computations, particularly modular multiplicative inverse.

Functions

find_mod_inverse(→ int)

Find the modular multiplicative inverse of a modulo m.

Module Contents

ciphers.cryptomath_module.find_mod_inverse(a: int, m: int) → int

Find the modular multiplicative inverse of a modulo m.

The modular multiplicative inverse of a modulo m is an integer x such that: (a * x) % m = 1

This function uses the Extended Euclidean Algorithm to find the inverse. An inverse exists if and only if a and m are coprime (gcd(a, m) = 1).

Args:

a: The integer to find the inverse of m: The modulus

Returns:

The modular multiplicative inverse of a modulo m

Raises:

ValueError: If gcd(a, m) != 1 (inverse does not exist)

Reference:

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Examples: >>> find_mod_inverse(3, 7) 5 >>> (3 * 5) % 7 # Verify: 3 * 5 ≡ 1 (mod 7) 1 >>> find_mod_inverse(3, 10) 7 >>> (3 * 7) % 10 # Verify: 3 * 7 ≡ 1 (mod 10) 1 >>> find_mod_inverse(4, 11) 3 >>> (4 * 3) % 11 # Verify: 4 * 3 ≡ 1 (mod 11) 1 >>> find_mod_inverse(7, 26) 15 >>> (7 * 15) % 26 # Verify: 7 * 15 ≡ 1 (mod 26) 1 >>> find_mod_inverse(1, 5) 1 >>> find_mod_inverse(2, 7) 4 >>> find_mod_inverse(3, 11) 4 >>> find_mod_inverse(5, 11) 9 >>> find_mod_inverse(5, 17) 7 >>> find_mod_inverse(2, 4) Traceback (most recent call last):

…

ValueError: mod inverse of 2 and 4 does not exist >>> find_mod_inverse(6, 9) Traceback (most recent call last):

…

ValueError: mod inverse of 6 and 9 does not exist >>> find_mod_inverse(10, 20) Traceback (most recent call last):

…

ValueError: mod inverse of 10 and 20 does not exist