unconnect
diff --git a/‎ciphers/rsa_factorization.py‎
Lines changed: 13 additions & 8 deletions b/‎ciphers/rsa_factorization.py‎
Lines changed: 13 additions & 8 deletions
@@ -4,6 +4,7 @@
 The program can efficiently factor RSA prime number given the private key d and
 public key e.
 Source: on page 3 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf
+More readable source: https://www.di-mgt.com.au/rsa_factorize_n.html
 large number can take minutes to factor, therefore are not included in doctest.
 """
 import math
@@ -15,7 +16,7 @@ def rsafactor(d: int, e: int, N: int) -> List[int]:
     """
     This function returns the factors of N, where p*q=N
       Return: [p, q]
-    
+
     We call N the RSA modulus, e the encryption exponent, and d the decryption exponent.
     The pair (N, e) is the public key. As its name suggests, it is public and is used to
         encrypt messages.
@@ -35,13 +36,17 @@ def rsafactor(d: int, e: int, N: int) -> List[int]:
     while p == 0:
         g = random.randint(2, N - 1)
         t = k
-        if t % 2 == 0:
-            t = t // 2
-            x = (g ** t) % N
-            y = math.gcd(x - 1, N)
-            if x > 1 and y > 1:
-                p = y
-                q = N // y
+        while True:
+            if t % 2 == 0:
+                t = t // 2
+                x = (g ** t) % N
+                y = math.gcd(x - 1, N)
+                if x > 1 and y > 1:
+                    p = y
+                    q = N // y
+                    break  # find the correct factors
+            else:
+                break  # t is not divisible by 2, break and choose another g
     return sorted([p, q])