dが与えられた時にnに対して素因数分解を試みるやつ

given_d.py

from fractions import gcd
import random
from typing import Optional, Tuple


def given_d(n: int, e: int, d: int) -> Optional[Tuple[int, int]]:
    ktot = e * d - 1
    s = (ktot & -ktot).bit_length() - 1
    t = ktot >> s

    limit = 1000
    for _ in range(limit):
        a = random.randrange(2, n)
        x = pow(a, t, n)
        for i in range(s):
            y = x * x % n
            if x not in (1, n - 1) and y == 1:
                p = gcd(x + 1, n)
                assert n % p == 0
                
                return p, n // p
            x = y
    return None