An RSA prime factor algorithm. 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.edudabopapersRSAsurvey.pdf More readable source: https:www.dimgt.com.aursafactorizen.html large number can take minutes to factor, therefore are not included in doctest. This function returns the factors of N, where pqN 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. The pair N, d is the secret key or private key and is known only to the recipient of encrypted messages.  rsafactor3, 16971, 25777 149, 173  rsafactor7331, 11, 27233 113, 241  rsafactor4021, 13, 17711 89, 199
from __future__ import annotations

import math
import random


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.
    The pair (N, d) is the secret key or private key and is known only to the recipient
        of encrypted messages.

    >>> rsafactor(3, 16971, 25777)
    [149, 173]
    >>> rsafactor(7331, 11, 27233)
    [113, 241]
    >>> rsafactor(4021, 13, 17711)
    [89, 199]
    """
    k = d * e - 1
    p = 0
    q = 0
    while p == 0:
        g = random.randint(2, n - 1)
        t = k
        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])


if __name__ == "__main__":
    import doctest

    doctest.testmod()
