Toy RSA Key Math

RSA key generation relies on modular inverses:

 n = p * q
phi = (p-1)(q-1)
 d = e^{-1} mod phi

In this toy problem, p and q are assumed to be prime and small enough to fit in 64-bit integers.

Function signature

func RSAKeygen(p, q, e int64) (n, d int64, ok bool)

Requirements

• Return ok=false if p <= 1, q <= 1, e <= 1, or gcd(e, phi) != 1.
• If ok=true, return n = p*q and d in [1, phi-1].

Constraints

• 2 <= p, q <= 1e9
• 2 <= e <= 1e12
• Product p*q fits in int64

Notes

• This is not secure RSA. It is just the math step.