RSA - is it possible to find the modulus from both the private and public exponents? Let $e$ be the public exponent (which is equal to $65537$) and $d$ the private exponent. Knowing the values of those two, is it possible to deduce $N$, the modulus, and if yes, how?

Note: the value of $N$ is not known! I also don't need to get the values of $p$ and $q$, but seeing how $d$ is actually calculated makes me think it'd be easy to get them anyway.
It turns out that recovering $N$ from $e, d$ is a hard problem; in particular, if you can, you can factor values that are currently believed to be intractable (!).

To start with, a necessary and sufficient condition on $e, d$ being valid RSA exponents to a square-free modulus $N$ is that, for every prime factor $p$ of $N$, we have:

$$ed - 1 = k(p-1)$$

for some integer $k$.

Now, let us assume that we have an Oracle that, given $e, d$, will recover a value $N$ for which $e, d$ are valid RSA exponents (assuming there is such an $N$); we further assume that it gives a reasonably large value $N$, specifically, one in the range $\ell \sqrt{eq} &lt; N &lt; 5ed$ (for a modest constant $\ell$).

Now, suppose that we have a value $N = pq$, where $p, q$ are both unknown Sophie-Germain primes (that is, $2p+1$ and $2q+1$ are also prime), and are approximately the same size; that is $q &lt; p &lt; 2q$.  We will also assume that the value $2pq+1$ and $4pq+1$ both happen to be composite (which it will be for a majority of the possible $p, q$ pairs).

Assuming $N$ is sufficiently large, there is no known way to factor it.

We note that $p \equiv q \equiv 2 \pmod 3$, and hence $2N + 1$ is a multiple of 3.  So, we set $e = 3$ and $d = (2N + 1)/e$; and give $d, e$ to our Oracle.

What the Oracle will do is return a value $N' = p_1' p_2' … p_n' $ (where $p_1', p_2', …, p_n'$ is the prime factorization of $N'$.  Such an $N'$ will always exist, as $N' = (2p+1)(2q+1)$ is such a valid modulus (hence the Oracle must return some value, if not necessarily $(2p+1)(2q+1)$

Because of the condition on RSA exponents, we have $ed - 1 = 2pq = k_i(p_i' - 1)$ for every prime $p_i'$.

Because of the range limitation on $N'$ (that is, $\ell \sqrt{eq} &lt; N'$), we must have $p$ as one of the factors of $p_i' - 1$ (for some $i$), and similarly have $q$ as a factor of $p_j'-1$ (for some different $j$; it must be different, otherwise this prime factor would be $2kpq+1$; we assumed that $k=1$ and $k=2$ didn't yield a prime, and $k&gt;2$ have a value outside the $5ed$ range we assumed).

Hence, we have $N' = k''(k'''p + 1)(k''''q + 1)$, for modest $k'', k''', k''''$.  Given that, and $N = pq$, it's easy to factor $N$.

This is much more of a sketch than I originally intended; there are a number of missing details.  However it should not be hard to fill in the details...