gcd(phi, e) != 1のRSAで とかの場合にこれで解けるかも
ちなみにこんなことをしなくてもsageにはnth_rootが実装されていてそれで良いかも
import random def eth_root(x, e, p): """ Adleman-Manders-Miller e-th root extraction algorithm in Fp x: e-th residue in Fq e: exponent (e | p-1) p: prime """ assert is_prime(p) assert (p - 1) % e == 0 assert (p - 1) % (e**2) != 0 l = (p - 1) % (e**2) // e a = -inverse_mod(l, e) % e return pow(c, (1 + a * (p - 1) // e) // e, p) def all_roots(known_root, e, p): """ Find all e-th roots in Fp known_root: one of e-th root of something e: exponent size p: prime """ # primitive e-th roots proots = set() while len(proots) < e: proots.add(pow(randint(2, p-1), (p - 1) // e, p)) # all e-th roots roots = set() for root in proots: roots.add(known_root * root % p) return roots while True: p = random_prime(1<<128) q = random_prime(1<<128) n = p * q factors = [x**e for x,e in factor(p-1, limit=2**10) if 2**5 < x**e < 2**20] try: e = random.choice(factors) except IndexError: continue break m = randint(2, n-1) c = pow(m, e, n) print("p={}".format(p)) print("q={}".format(q)) print("e={}".format(e)) print("m={}".format(m)) print("c={}".format(c)) print("---") cp, cq = c % p, c % q mps = all_roots(eth_root(cp, e, p), e, p) mq = pow(cq, inverse_mod(e, q-1), q) for mp in mps: m_ = CRT_list([int(mp), int(mq)], [p, q]) if m_ == m: print("OK") quit() print("NG")
