switch to more compact modular multiplicative inverse
diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 9cb015b..a413f10 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -24,18 +24,17 @@
from ...utils import load_pkcs1_vectors, load_vectors_from_file
-def _egcd(a, b):
- if a == 0:
- return (b, 0, 1)
- else:
- g, y, x = _egcd(b % a, a)
- return (g, x - (b // a) * y, y)
-
-
-def _modinv(a, m):
- g, x, y = _egcd(a, m)
- assert g == 1
- return x % m
+def _modinv(e, m):
+ """
+ Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1
+ """
+ x1, y1, x2, y2 = 1, 0, 0, 1
+ a, b = e, m
+ while b > 0:
+ q, r = divmod(a, b)
+ xn, yn = x1 - q * x2, y1 - q * y2
+ a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
+ return x1 % m
def _check_rsa_private_key(skey):
@@ -56,21 +55,6 @@
assert skey.key_size == pkey.key_size
-def test_egcd():
- assert _egcd(0, 1) == (1, 0, 1)
- val = _egcd(
- int("c08e63c2fdf20bd2a05bd448e34a892cc8718c13ac5f8fb3f55cff7bc1a7f891",
- 16),
- int("e525d5ee4fe6d6142812fe12a7b531ebfaa033be349e4c3680d264f41d82008b",
- 16)
- )
- assert val[0] == 1
- assert val[1] == int("6caa1a8fae63ab2b8d4051101828985ef93fb0ffc14a955f93fd"
- "9c4a3fd8c7b1", 16)
- assert val[2] == int("-5b4ff48d0c09936986bc3c544f1e7dd684f8c0f09ae36a7819e"
- "c95017c4be1c0", 16)
-
-
def test_modular_inverse():
p = int(
"d1f9f6c09fd3d38987f7970247b85a6da84907753d42ec52bc23b745093f4fff5cff3"