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 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 find the correct factors t is not divisible by 2 break and choose another g
from __future__ import annotations

import math
import random


def rsafactor(d: int, e: int, n: int) -> list[int]:
    
    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  
            else:
                break  
    return sorted([p, q])


if __name__ == "__main__":
    import doctest

    doctest.testmod()