Given a positive integer \$N >= 4\$, output an RSA key pair (both the private and the public key) whose key length is \$N\$ bits.
The RSA key generation algorithm is as follows:
- Choose an \$N\$-bit semiprime \$n\$. Let the prime factors of \$n\$ be \$p\$ and \$q\$.
- Compute \$\lambda(n) = LCM(p-1, q-1)\$.
- Choose an integer \$e\$ such that \$1 < e < \lambda(n)\$ and \$GCD(e, \lambda(n)) = 1\$.
- Compute \$d \equiv e^{−1} \pmod {\lambda(n)}\$.
The public key is composed of \$n\$ and \$e\$. The private key is \$d\$.
Rules
- You may assume that there exists at least one semiprime \$n\$ with bit length \$N\$.
- Output may be in any consistent and unambiguous format.
- \$e\$ and \$n\$ must be chosen from discrete uniform distributions.
- You may assume that \$N\$ is less than or equal to the maximum number of bits for integers representable in your language, if your language has such a restriction.