# How do I recover RSA primes from the modulus and the coefficient?

The RSA private key contains 2 primes (of about 4096 bits each), and I only know their product (called modulus) and the modular inverse (called coefficient).

How do I recover the RSA primes from the modulus and the coefficient, i.e. how do I implement get_primes below?

def get_modulus_and_coefficient(prime1, prime2):
assert prime1 > prime2
coefficient = modinv(prime2, prime1)  # Modular inverse of prime2 modulo prime1.
assert coefficient * prime2 % prime1 == 1
modulus = prime1 * prime2
return modulus, coefficient

def get_primes(modulus, coefficient):
... prime1, prime2 = ...
assert get_modulus_and_coefficient(prime1, prime2) == (modulus, coefficient)
return prime1, prime2


Is there a well known-recovery method published for this?

FYI This question is different from https://crypto.stackexchange.com/a/25910 . The other question asks for recovery of the primes $$p_1$$ and $$p_2$$ from $$n$$, $$e$$, $$d$$. This question asks for recovery of the primes $$p_1$$ and $$p_2$$ from $$n$$ and $$q_\mathrm{inv}=p_2^{-1}\mod p_1$$. The answer for the other question doesn't help at all with this question.