switch to more compact modular multiplicative inverse

1 files changed, 11 insertions, 27 deletions

diff --git a/tests/hazmat/primitives/test_rsa.py b/tests/hazmat/primitives/test_rsa.py
index 9cb015b7..a413f10b 100644
--- a/tests/hazmat/primitives/test_rsa.py
+++ b/tests/hazmat/primitives/test_rsa.py
@@ -24,18 +24,17 @@ from cryptography.hazmat.primitives.asymmetric import rsa
 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 @@ def _check_rsa_private_key(skey):
     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"