We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
[RSA] Add functions to recover (p, q) given (n, e, d)
Right now we require (p, q, d, dmp1, dmq1, iqmp, e, n). We provide functions to generate the CRT coefficients, but they assume the user has p & q. To support other valid key material sources we need functions that recover p & q given (n, e, d).

The preferred algorithm to perform this task can be found in Appendix C of [SP-800-56B](http://csrc.nist.gov/publications/nistpubs/800-56B/sp800-56B.pdf).

[RSA] Add functions to recover (p, q) given (n, e, d)
Right now we require (p, q, d, dmp1, dmq1, iqmp, e, n). We provide functions to generate the CRT coefficients, but they assume the user has p & q. To support other valid key material sources we need functions that recover p & q given (n, e, d).

The preferred algorithm to perform this task can be found in Appendix C of [SP-800-56B](http://csrc.nist.gov/publications/nistpubs/800-56B/sp800-56B.pdf).


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `src/cryptography/hazmat/primitives/asymmetric/rsa.py`
Content:
```
1 # This file is dual licensed under the terms of the Apache License, Version
2 # 2.0, and the BSD License. See the LICENSE file in the root of this repository
3 # for complete details.
4 
5 from __future__ import absolute_import, division, print_function
6 
7 import six
8 
9 from cryptography import utils
10 from cryptography.exceptions import UnsupportedAlgorithm, _Reasons
11 from cryptography.hazmat.backends.interfaces import RSABackend
12 
13 
14 def generate_private_key(public_exponent, key_size, backend):
15     if not isinstance(backend, RSABackend):
16         raise UnsupportedAlgorithm(
17             "Backend object does not implement RSABackend.",
18             _Reasons.BACKEND_MISSING_INTERFACE
19         )
20 
21     _verify_rsa_parameters(public_exponent, key_size)
22     return backend.generate_rsa_private_key(public_exponent, key_size)
23 
24 
25 def _verify_rsa_parameters(public_exponent, key_size):
26     if public_exponent < 3:
27         raise ValueError("public_exponent must be >= 3.")
28 
29     if public_exponent & 1 == 0:
30         raise ValueError("public_exponent must be odd.")
31 
32     if key_size < 512:
33         raise ValueError("key_size must be at least 512-bits.")
34 
35 
36 def _check_private_key_components(p, q, private_exponent, dmp1, dmq1, iqmp,
37                                   public_exponent, modulus):
38     if modulus < 3:
39         raise ValueError("modulus must be >= 3.")
40 
41     if p >= modulus:
42         raise ValueError("p must be < modulus.")
43 
44     if q >= modulus:
45         raise ValueError("q must be < modulus.")
46 
47     if dmp1 >= modulus:
48         raise ValueError("dmp1 must be < modulus.")
49 
50     if dmq1 >= modulus:
51         raise ValueError("dmq1 must be < modulus.")
52 
53     if iqmp >= modulus:
54         raise ValueError("iqmp must be < modulus.")
55 
56     if private_exponent >= modulus:
57         raise ValueError("private_exponent must be < modulus.")
58 
59     if public_exponent < 3 or public_exponent >= modulus:
60         raise ValueError("public_exponent must be >= 3 and < modulus.")
61 
62     if public_exponent & 1 == 0:
63         raise ValueError("public_exponent must be odd.")
64 
65     if dmp1 & 1 == 0:
66         raise ValueError("dmp1 must be odd.")
67 
68     if dmq1 & 1 == 0:
69         raise ValueError("dmq1 must be odd.")
70 
71     if p * q != modulus:
72         raise ValueError("p*q must equal modulus.")
73 
74 
75 def _check_public_key_components(e, n):
76     if n < 3:
77         raise ValueError("n must be >= 3.")
78 
79     if e < 3 or e >= n:
80         raise ValueError("e must be >= 3 and < n.")
81 
82     if e & 1 == 0:
83         raise ValueError("e must be odd.")
84 
85 
86 def _modinv(e, m):
87     """
88     Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1
89     """
90     x1, y1, x2, y2 = 1, 0, 0, 1
91     a, b = e, m
92     while b > 0:
93         q, r = divmod(a, b)
94         xn, yn = x1 - q * x2, y1 - q * y2
95         a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn
96     return x1 % m
97 
98 
99 def rsa_crt_iqmp(p, q):
100     """
101     Compute the CRT (q ** -1) % p value from RSA primes p and q.
102     """
103     return _modinv(q, p)
104 
105 
106 def rsa_crt_dmp1(private_exponent, p):
107     """
108     Compute the CRT private_exponent % (p - 1) value from the RSA
109     private_exponent and p.
110     """
111     return private_exponent % (p - 1)
112 
113 
114 def rsa_crt_dmq1(private_exponent, q):
115     """
116     Compute the CRT private_exponent % (q - 1) value from the RSA
117     private_exponent and q.
118     """
119     return private_exponent % (q - 1)
120 
121 
122 class RSAPrivateNumbers(object):
123     def __init__(self, p, q, d, dmp1, dmq1, iqmp,
124                  public_numbers):
125         if (
126             not isinstance(p, six.integer_types) or
127             not isinstance(q, six.integer_types) or
128             not isinstance(d, six.integer_types) or
129             not isinstance(dmp1, six.integer_types) or
130             not isinstance(dmq1, six.integer_types) or
131             not isinstance(iqmp, six.integer_types)
132         ):
133             raise TypeError(
134                 "RSAPrivateNumbers p, q, d, dmp1, dmq1, iqmp arguments must"
135                 " all be an integers."
136             )
137 
138         if not isinstance(public_numbers, RSAPublicNumbers):
139             raise TypeError(
140                 "RSAPrivateNumbers public_numbers must be an RSAPublicNumbers"
141                 " instance."
142             )
143 
144         self._p = p
145         self._q = q
146         self._d = d
147         self._dmp1 = dmp1
148         self._dmq1 = dmq1
149         self._iqmp = iqmp
150         self._public_numbers = public_numbers
151 
152     p = utils.read_only_property("_p")
153     q = utils.read_only_property("_q")
154     d = utils.read_only_property("_d")
155     dmp1 = utils.read_only_property("_dmp1")
156     dmq1 = utils.read_only_property("_dmq1")
157     iqmp = utils.read_only_property("_iqmp")
158     public_numbers = utils.read_only_property("_public_numbers")
159 
160     def private_key(self, backend):
161         return backend.load_rsa_private_numbers(self)
162 
163     def __eq__(self, other):
164         if not isinstance(other, RSAPrivateNumbers):
165             return NotImplemented
166 
167         return (
168             self.p == other.p and
169             self.q == other.q and
170             self.d == other.d and
171             self.dmp1 == other.dmp1 and
172             self.dmq1 == other.dmq1 and
173             self.iqmp == other.iqmp and
174             self.public_numbers == other.public_numbers
175         )
176 
177     def __ne__(self, other):
178         return not self == other
179 
180 
181 class RSAPublicNumbers(object):
182     def __init__(self, e, n):
183         if (
184             not isinstance(e, six.integer_types) or
185             not isinstance(n, six.integer_types)
186         ):
187             raise TypeError("RSAPublicNumbers arguments must be integers.")
188 
189         self._e = e
190         self._n = n
191 
192     e = utils.read_only_property("_e")
193     n = utils.read_only_property("_n")
194 
195     def public_key(self, backend):
196         return backend.load_rsa_public_numbers(self)
197 
198     def __repr__(self):
199         return "<RSAPublicNumbers(e={0}, n={1})>".format(self._e, self._n)
200 
201     def __eq__(self, other):
202         if not isinstance(other, RSAPublicNumbers):
203             return NotImplemented
204 
205         return self.e == other.e and self.n == other.n
206 
207     def __ne__(self, other):
208         return not self == other
209
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py
--- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py
+++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py
@@ -4,6 +4,8 @@
 
 from __future__ import absolute_import, division, print_function
 
+from fractions import gcd
+
 import six
 
 from cryptography import utils
@@ -119,6 +121,55 @@
     return private_exponent % (q - 1)
 
 
+# Controls the number of iterations rsa_recover_prime_factors will perform
+# to obtain the prime factors. Each iteration increments by 2 so the actual
+# maximum attempts is half this number.
+_MAX_RECOVERY_ATTEMPTS = 1000
+
+
+def rsa_recover_prime_factors(n, e, d):
+    """
+    Compute factors p and q from the private exponent d. We assume that n has
+    no more than two factors. This function is adapted from code in PyCrypto.
+    """
+    # See 8.2.2(i) in Handbook of Applied Cryptography.
+    ktot = d * e - 1
+    # The quantity d*e-1 is a multiple of phi(n), even,
+    # and can be represented as t*2^s.
+    t = ktot
+    while t % 2 == 0:
+        t = t // 2
+    # Cycle through all multiplicative inverses in Zn.
+    # The algorithm is non-deterministic, but there is a 50% chance
+    # any candidate a leads to successful factoring.
+    # See "Digitalized Signatures and Public Key Functions as Intractable
+    # as Factorization", M. Rabin, 1979
+    spotted = False
+    a = 2
+    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:
+        k = t
+        # Cycle through all values a^{t*2^i}=a^k
+        while k < ktot:
+            cand = pow(a, k, n)
+            # Check if a^k is a non-trivial root of unity (mod n)
+            if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:
+                # We have found a number such that (cand-1)(cand+1)=0 (mod n).
+                # Either of the terms divides n.
+                p = gcd(cand + 1, n)
+                spotted = True
+                break
+            k *= 2
+        # This value was not any good... let's try another!
+        a += 2
+    if not spotted:
+        raise ValueError("Unable to compute factors p and q from exponent d.")
+    # Found !
+    q, r = divmod(n, p)
+    assert r == 0
+
+    return (p, q)
+
+
 class RSAPrivateNumbers(object):
     def __init__(self, p, q, d, dmp1, dmq1, iqmp,
                  public_numbers):

{"golden_diff": "diff --git a/src/cryptography/hazmat/primitives/asymmetric/rsa.py b/src/cryptography/hazmat/primitives/asymmetric/rsa.py\n--- a/src/cryptography/hazmat/primitives/asymmetric/rsa.py\n+++ b/src/cryptography/hazmat/primitives/asymmetric/rsa.py\n@@ -4,6 +4,8 @@\n \n from __future__ import absolute_import, division, print_function\n \n+from fractions import gcd\n+\n import six\n \n from cryptography import utils\n@@ -119,6 +121,55 @@\n     return private_exponent % (q - 1)\n \n \n+# Controls the number of iterations rsa_recover_prime_factors will perform\n+# to obtain the prime factors. Each iteration increments by 2 so the actual\n+# maximum attempts is half this number.\n+_MAX_RECOVERY_ATTEMPTS = 1000\n+\n+\n+def rsa_recover_prime_factors(n, e, d):\n+    \"\"\"\n+    Compute factors p and q from the private exponent d. We assume that n has\n+    no more than two factors. This function is adapted from code in PyCrypto.\n+    \"\"\"\n+    # See 8.2.2(i) in Handbook of Applied Cryptography.\n+    ktot = d * e - 1\n+    # The quantity d*e-1 is a multiple of phi(n), even,\n+    # and can be represented as t*2^s.\n+    t = ktot\n+    while t % 2 == 0:\n+        t = t // 2\n+    # Cycle through all multiplicative inverses in Zn.\n+    # The algorithm is non-deterministic, but there is a 50% chance\n+    # any candidate a leads to successful factoring.\n+    # See \"Digitalized Signatures and Public Key Functions as Intractable\n+    # as Factorization\", M. Rabin, 1979\n+    spotted = False\n+    a = 2\n+    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:\n+        k = t\n+        # Cycle through all values a^{t*2^i}=a^k\n+        while k < ktot:\n+            cand = pow(a, k, n)\n+            # Check if a^k is a non-trivial root of unity (mod n)\n+            if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:\n+                # We have found a number such that (cand-1)(cand+1)=0 (mod n).\n+                # Either of the terms divides n.\n+                p = gcd(cand + 1, n)\n+                spotted = True\n+                break\n+            k *= 2\n+        # This value was not any good... let's try another!\n+        a += 2\n+    if not spotted:\n+        raise ValueError(\"Unable to compute factors p and q from exponent d.\")\n+    # Found !\n+    q, r = divmod(n, p)\n+    assert r == 0\n+\n+    return (p, q)\n+\n+\n class RSAPrivateNumbers(object):\n     def __init__(self, p, q, d, dmp1, dmq1, iqmp,\n                  public_numbers):\n", "issue": "[RSA] Add functions to recover (p, q) given (n, e, d)\nRight now we require (p, q, d, dmp1, dmq1, iqmp, e, n). We provide functions to generate the CRT coefficients, but they assume the user has p & q. To support other valid key material sources we need functions that recover p & q given (n, e, d).\n\nThe preferred algorithm to perform this task can be found in Appendix C of [SP-800-56B](http://csrc.nist.gov/publications/nistpubs/800-56B/sp800-56B.pdf).\n\n[RSA] Add functions to recover (p, q) given (n, e, d)\nRight now we require (p, q, d, dmp1, dmq1, iqmp, e, n). We provide functions to generate the CRT coefficients, but they assume the user has p & q. To support other valid key material sources we need functions that recover p & q given (n, e, d).\n\nThe preferred algorithm to perform this task can be found in Appendix C of [SP-800-56B](http://csrc.nist.gov/publications/nistpubs/800-56B/sp800-56B.pdf).\n\n", "before_files": [{"content": "# This file is dual licensed under the terms of the Apache License, Version\n# 2.0, and the BSD License. See the LICENSE file in the root of this repository\n# for complete details.\n\nfrom __future__ import absolute_import, division, print_function\n\nimport six\n\nfrom cryptography import utils\nfrom cryptography.exceptions import UnsupportedAlgorithm, _Reasons\nfrom cryptography.hazmat.backends.interfaces import RSABackend\n\n\ndef generate_private_key(public_exponent, key_size, backend):\n    if not isinstance(backend, RSABackend):\n        raise UnsupportedAlgorithm(\n            \"Backend object does not implement RSABackend.\",\n            _Reasons.BACKEND_MISSING_INTERFACE\n        )\n\n    _verify_rsa_parameters(public_exponent, key_size)\n    return backend.generate_rsa_private_key(public_exponent, key_size)\n\n\ndef _verify_rsa_parameters(public_exponent, key_size):\n    if public_exponent < 3:\n        raise ValueError(\"public_exponent must be >= 3.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if key_size < 512:\n        raise ValueError(\"key_size must be at least 512-bits.\")\n\n\ndef _check_private_key_components(p, q, private_exponent, dmp1, dmq1, iqmp,\n                                  public_exponent, modulus):\n    if modulus < 3:\n        raise ValueError(\"modulus must be >= 3.\")\n\n    if p >= modulus:\n        raise ValueError(\"p must be < modulus.\")\n\n    if q >= modulus:\n        raise ValueError(\"q must be < modulus.\")\n\n    if dmp1 >= modulus:\n        raise ValueError(\"dmp1 must be < modulus.\")\n\n    if dmq1 >= modulus:\n        raise ValueError(\"dmq1 must be < modulus.\")\n\n    if iqmp >= modulus:\n        raise ValueError(\"iqmp must be < modulus.\")\n\n    if private_exponent >= modulus:\n        raise ValueError(\"private_exponent must be < modulus.\")\n\n    if public_exponent < 3 or public_exponent >= modulus:\n        raise ValueError(\"public_exponent must be >= 3 and < modulus.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if dmp1 & 1 == 0:\n        raise ValueError(\"dmp1 must be odd.\")\n\n    if dmq1 & 1 == 0:\n        raise ValueError(\"dmq1 must be odd.\")\n\n    if p * q != modulus:\n        raise ValueError(\"p*q must equal modulus.\")\n\n\ndef _check_public_key_components(e, n):\n    if n < 3:\n        raise ValueError(\"n must be >= 3.\")\n\n    if e < 3 or e >= n:\n        raise ValueError(\"e must be >= 3 and < n.\")\n\n    if e & 1 == 0:\n        raise ValueError(\"e must be odd.\")\n\n\ndef _modinv(e, m):\n    \"\"\"\n    Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1\n    \"\"\"\n    x1, y1, x2, y2 = 1, 0, 0, 1\n    a, b = e, m\n    while b > 0:\n        q, r = divmod(a, b)\n        xn, yn = x1 - q * x2, y1 - q * y2\n        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn\n    return x1 % m\n\n\ndef rsa_crt_iqmp(p, q):\n    \"\"\"\n    Compute the CRT (q ** -1) % p value from RSA primes p and q.\n    \"\"\"\n    return _modinv(q, p)\n\n\ndef rsa_crt_dmp1(private_exponent, p):\n    \"\"\"\n    Compute the CRT private_exponent % (p - 1) value from the RSA\n    private_exponent and p.\n    \"\"\"\n    return private_exponent % (p - 1)\n\n\ndef rsa_crt_dmq1(private_exponent, q):\n    \"\"\"\n    Compute the CRT private_exponent % (q - 1) value from the RSA\n    private_exponent and q.\n    \"\"\"\n    return private_exponent % (q - 1)\n\n\nclass RSAPrivateNumbers(object):\n    def __init__(self, p, q, d, dmp1, dmq1, iqmp,\n                 public_numbers):\n        if (\n            not isinstance(p, six.integer_types) or\n            not isinstance(q, six.integer_types) or\n            not isinstance(d, six.integer_types) or\n            not isinstance(dmp1, six.integer_types) or\n            not isinstance(dmq1, six.integer_types) or\n            not isinstance(iqmp, six.integer_types)\n        ):\n            raise TypeError(\n                \"RSAPrivateNumbers p, q, d, dmp1, dmq1, iqmp arguments must\"\n                \" all be an integers.\"\n            )\n\n        if not isinstance(public_numbers, RSAPublicNumbers):\n            raise TypeError(\n                \"RSAPrivateNumbers public_numbers must be an RSAPublicNumbers\"\n                \" instance.\"\n            )\n\n        self._p = p\n        self._q = q\n        self._d = d\n        self._dmp1 = dmp1\n        self._dmq1 = dmq1\n        self._iqmp = iqmp\n        self._public_numbers = public_numbers\n\n    p = utils.read_only_property(\"_p\")\n    q = utils.read_only_property(\"_q\")\n    d = utils.read_only_property(\"_d\")\n    dmp1 = utils.read_only_property(\"_dmp1\")\n    dmq1 = utils.read_only_property(\"_dmq1\")\n    iqmp = utils.read_only_property(\"_iqmp\")\n    public_numbers = utils.read_only_property(\"_public_numbers\")\n\n    def private_key(self, backend):\n        return backend.load_rsa_private_numbers(self)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPrivateNumbers):\n            return NotImplemented\n\n        return (\n            self.p == other.p and\n            self.q == other.q and\n            self.d == other.d and\n            self.dmp1 == other.dmp1 and\n            self.dmq1 == other.dmq1 and\n            self.iqmp == other.iqmp and\n            self.public_numbers == other.public_numbers\n        )\n\n    def __ne__(self, other):\n        return not self == other\n\n\nclass RSAPublicNumbers(object):\n    def __init__(self, e, n):\n        if (\n            not isinstance(e, six.integer_types) or\n            not isinstance(n, six.integer_types)\n        ):\n            raise TypeError(\"RSAPublicNumbers arguments must be integers.\")\n\n        self._e = e\n        self._n = n\n\n    e = utils.read_only_property(\"_e\")\n    n = utils.read_only_property(\"_n\")\n\n    def public_key(self, backend):\n        return backend.load_rsa_public_numbers(self)\n\n    def __repr__(self):\n        return \"<RSAPublicNumbers(e={0}, n={1})>\".format(self._e, self._n)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPublicNumbers):\n            return NotImplemented\n\n        return self.e == other.e and self.n == other.n\n\n    def __ne__(self, other):\n        return not self == other\n", "path": "src/cryptography/hazmat/primitives/asymmetric/rsa.py"}], "after_files": [{"content": "# This file is dual licensed under the terms of the Apache License, Version\n# 2.0, and the BSD License. See the LICENSE file in the root of this repository\n# for complete details.\n\nfrom __future__ import absolute_import, division, print_function\n\nfrom fractions import gcd\n\nimport six\n\nfrom cryptography import utils\nfrom cryptography.exceptions import UnsupportedAlgorithm, _Reasons\nfrom cryptography.hazmat.backends.interfaces import RSABackend\n\n\ndef generate_private_key(public_exponent, key_size, backend):\n    if not isinstance(backend, RSABackend):\n        raise UnsupportedAlgorithm(\n            \"Backend object does not implement RSABackend.\",\n            _Reasons.BACKEND_MISSING_INTERFACE\n        )\n\n    _verify_rsa_parameters(public_exponent, key_size)\n    return backend.generate_rsa_private_key(public_exponent, key_size)\n\n\ndef _verify_rsa_parameters(public_exponent, key_size):\n    if public_exponent < 3:\n        raise ValueError(\"public_exponent must be >= 3.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if key_size < 512:\n        raise ValueError(\"key_size must be at least 512-bits.\")\n\n\ndef _check_private_key_components(p, q, private_exponent, dmp1, dmq1, iqmp,\n                                  public_exponent, modulus):\n    if modulus < 3:\n        raise ValueError(\"modulus must be >= 3.\")\n\n    if p >= modulus:\n        raise ValueError(\"p must be < modulus.\")\n\n    if q >= modulus:\n        raise ValueError(\"q must be < modulus.\")\n\n    if dmp1 >= modulus:\n        raise ValueError(\"dmp1 must be < modulus.\")\n\n    if dmq1 >= modulus:\n        raise ValueError(\"dmq1 must be < modulus.\")\n\n    if iqmp >= modulus:\n        raise ValueError(\"iqmp must be < modulus.\")\n\n    if private_exponent >= modulus:\n        raise ValueError(\"private_exponent must be < modulus.\")\n\n    if public_exponent < 3 or public_exponent >= modulus:\n        raise ValueError(\"public_exponent must be >= 3 and < modulus.\")\n\n    if public_exponent & 1 == 0:\n        raise ValueError(\"public_exponent must be odd.\")\n\n    if dmp1 & 1 == 0:\n        raise ValueError(\"dmp1 must be odd.\")\n\n    if dmq1 & 1 == 0:\n        raise ValueError(\"dmq1 must be odd.\")\n\n    if p * q != modulus:\n        raise ValueError(\"p*q must equal modulus.\")\n\n\ndef _check_public_key_components(e, n):\n    if n < 3:\n        raise ValueError(\"n must be >= 3.\")\n\n    if e < 3 or e >= n:\n        raise ValueError(\"e must be >= 3 and < n.\")\n\n    if e & 1 == 0:\n        raise ValueError(\"e must be odd.\")\n\n\ndef _modinv(e, m):\n    \"\"\"\n    Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1\n    \"\"\"\n    x1, y1, x2, y2 = 1, 0, 0, 1\n    a, b = e, m\n    while b > 0:\n        q, r = divmod(a, b)\n        xn, yn = x1 - q * x2, y1 - q * y2\n        a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn\n    return x1 % m\n\n\ndef rsa_crt_iqmp(p, q):\n    \"\"\"\n    Compute the CRT (q ** -1) % p value from RSA primes p and q.\n    \"\"\"\n    return _modinv(q, p)\n\n\ndef rsa_crt_dmp1(private_exponent, p):\n    \"\"\"\n    Compute the CRT private_exponent % (p - 1) value from the RSA\n    private_exponent and p.\n    \"\"\"\n    return private_exponent % (p - 1)\n\n\ndef rsa_crt_dmq1(private_exponent, q):\n    \"\"\"\n    Compute the CRT private_exponent % (q - 1) value from the RSA\n    private_exponent and q.\n    \"\"\"\n    return private_exponent % (q - 1)\n\n\n# Controls the number of iterations rsa_recover_prime_factors will perform\n# to obtain the prime factors. Each iteration increments by 2 so the actual\n# maximum attempts is half this number.\n_MAX_RECOVERY_ATTEMPTS = 1000\n\n\ndef rsa_recover_prime_factors(n, e, d):\n    \"\"\"\n    Compute factors p and q from the private exponent d. We assume that n has\n    no more than two factors. This function is adapted from code in PyCrypto.\n    \"\"\"\n    # See 8.2.2(i) in Handbook of Applied Cryptography.\n    ktot = d * e - 1\n    # The quantity d*e-1 is a multiple of phi(n), even,\n    # and can be represented as t*2^s.\n    t = ktot\n    while t % 2 == 0:\n        t = t // 2\n    # Cycle through all multiplicative inverses in Zn.\n    # The algorithm is non-deterministic, but there is a 50% chance\n    # any candidate a leads to successful factoring.\n    # See \"Digitalized Signatures and Public Key Functions as Intractable\n    # as Factorization\", M. Rabin, 1979\n    spotted = False\n    a = 2\n    while not spotted and a < _MAX_RECOVERY_ATTEMPTS:\n        k = t\n        # Cycle through all values a^{t*2^i}=a^k\n        while k < ktot:\n            cand = pow(a, k, n)\n            # Check if a^k is a non-trivial root of unity (mod n)\n            if cand != 1 and cand != (n - 1) and pow(cand, 2, n) == 1:\n                # We have found a number such that (cand-1)(cand+1)=0 (mod n).\n                # Either of the terms divides n.\n                p = gcd(cand + 1, n)\n                spotted = True\n                break\n            k *= 2\n        # This value was not any good... let's try another!\n        a += 2\n    if not spotted:\n        raise ValueError(\"Unable to compute factors p and q from exponent d.\")\n    # Found !\n    q, r = divmod(n, p)\n    assert r == 0\n\n    return (p, q)\n\n\nclass RSAPrivateNumbers(object):\n    def __init__(self, p, q, d, dmp1, dmq1, iqmp,\n                 public_numbers):\n        if (\n            not isinstance(p, six.integer_types) or\n            not isinstance(q, six.integer_types) or\n            not isinstance(d, six.integer_types) or\n            not isinstance(dmp1, six.integer_types) or\n            not isinstance(dmq1, six.integer_types) or\n            not isinstance(iqmp, six.integer_types)\n        ):\n            raise TypeError(\n                \"RSAPrivateNumbers p, q, d, dmp1, dmq1, iqmp arguments must\"\n                \" all be an integers.\"\n            )\n\n        if not isinstance(public_numbers, RSAPublicNumbers):\n            raise TypeError(\n                \"RSAPrivateNumbers public_numbers must be an RSAPublicNumbers\"\n                \" instance.\"\n            )\n\n        self._p = p\n        self._q = q\n        self._d = d\n        self._dmp1 = dmp1\n        self._dmq1 = dmq1\n        self._iqmp = iqmp\n        self._public_numbers = public_numbers\n\n    p = utils.read_only_property(\"_p\")\n    q = utils.read_only_property(\"_q\")\n    d = utils.read_only_property(\"_d\")\n    dmp1 = utils.read_only_property(\"_dmp1\")\n    dmq1 = utils.read_only_property(\"_dmq1\")\n    iqmp = utils.read_only_property(\"_iqmp\")\n    public_numbers = utils.read_only_property(\"_public_numbers\")\n\n    def private_key(self, backend):\n        return backend.load_rsa_private_numbers(self)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPrivateNumbers):\n            return NotImplemented\n\n        return (\n            self.p == other.p and\n            self.q == other.q and\n            self.d == other.d and\n            self.dmp1 == other.dmp1 and\n            self.dmq1 == other.dmq1 and\n            self.iqmp == other.iqmp and\n            self.public_numbers == other.public_numbers\n        )\n\n    def __ne__(self, other):\n        return not self == other\n\n\nclass RSAPublicNumbers(object):\n    def __init__(self, e, n):\n        if (\n            not isinstance(e, six.integer_types) or\n            not isinstance(n, six.integer_types)\n        ):\n            raise TypeError(\"RSAPublicNumbers arguments must be integers.\")\n\n        self._e = e\n        self._n = n\n\n    e = utils.read_only_property(\"_e\")\n    n = utils.read_only_property(\"_n\")\n\n    def public_key(self, backend):\n        return backend.load_rsa_public_numbers(self)\n\n    def __repr__(self):\n        return \"<RSAPublicNumbers(e={0}, n={1})>\".format(self._e, self._n)\n\n    def __eq__(self, other):\n        if not isinstance(other, RSAPublicNumbers):\n            return NotImplemented\n\n        return self.e == other.e and self.n == other.n\n\n    def __ne__(self, other):\n        return not self == other\n", "path": "src/cryptography/hazmat/primitives/asymmetric/rsa.py"}]}