mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
Pranav LawateandChristian Clauss
84c57843bb
- Added detailed docstring explaining modular multiplicative inverse - Included 10 valid test cases with verification calculations - Added 3 error cases testing ValueError for non-coprime inputs - Added Wikipedia reference for educational value - All doctests pass locally (python -m doctest -v) - Passes ruff, mypy, and pre-commit hooks Contributes to #9943 Co-authored-by: Christian Clauss <cclauss@me.com>
83 lines
2.2 KiB
Python
83 lines
2.2 KiB
Python
"""
|
|
Cryptographic mathematics module for modular arithmetic operations.
|
|
|
|
This module provides utilities for cryptographic computations,
|
|
particularly modular multiplicative inverse.
|
|
"""
|
|
|
|
from maths.greatest_common_divisor import gcd_by_iterative
|
|
|
|
|
|
def 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
|
|
"""
|
|
if gcd_by_iterative(a, m) != 1:
|
|
msg = f"mod inverse of {a!r} and {m!r} does not exist"
|
|
raise ValueError(msg)
|
|
u1, u2, u3 = 1, 0, a
|
|
v1, v2, v3 = 0, 1, m
|
|
while v3 != 0:
|
|
q = u3 // v3
|
|
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
|
|
return u1 % m
|