Calculating RSA Public Modulus from Private Exponent and Public Exponent If I know the private and public exponents ($d$ and $e$) of an RSA key pair, is it possible to (efficiently) calculate the public modulus $n$?
Summary: finding $n$ from $(e,d)$ is computationally feasible with fair probability, or even certainty, for a small but observable fraction of RSA keys of practical interest, including with a modulus much too large to be factored.
I'll assume

unknown $n=p\,q$ with $p$ and $q$ unknown distinct large primes of comparable order of magnitude, say $\max(p,q)&lt;2\min(p,q)$.
given $(e,d)$ with small $e$ (e.g. one of the 5 Fermat primes).
a known one of $d=e^{-1}\bmod\varphi(n)$ (as often in textbook RSA) or $d=e^{-1}\bmod\lambda(n)$ (as in FIPS 186-4) holds.

It follows from their respective definition that $\varphi(n)=(p-1)(q-1)$ and $\lambda(n)=\varphi(n)/g$, with $g=\gcd(p-1,q-1)$.
It holds $h\,(p-1)(q-1)=(e\,d-1)$ or $h\,(p-1)(q-1)=g\,(e\,d-1)$ for some unknown $h&lt;e$, and a $g$ that can be found by enumeration, for it is a small even integer, often $2$ (always in some key generation strategies), rarely above $10$.
In the cases where we can fully factor $e\,d-1$, that will leave an enumerable number of options for re-arranging its factors into $p-1$, $q-1$ and $h$. Given the size and primality constraints on $p$ and $q$, few possibilities will remain, often a single one. $n$ follows.
That can sometime work in cases where the best factorization obtained for $e\,d-1$ is partial, but we are lucky enough that the remaining large composite has all its factors in a single of $p-1$ or $q-1$. This is possible only if that remaining composite is less than $\max(p,q)$, and then only with low probability.
The proportion of keys where the methods works depends on the modulus size, on how hard we are willing to try to factor $e\,d-1$, and on how the primes $p$ and $q$ have been generated (in particular: at random, or with a large known prime factor in $p-1$ and $q-1$ in consideration of Pollard's p-1 factorization. In the later case, the magnitude of that factor will be important. If high (e.g. 60% of the bit size of the primes), the task will be hard; but typical parametrization is lower).
The factorization strategy could be similar to that for arbitrary integers:

pull the small factors of $e\,d-1$ by trial division.
pull more small factors by Pollard's rho
optionally but somewhat advantageously, some Pollard's p-1.
optionally but still somewhat advantageously, some William's p+1.
a lot of ECM, where most of the effort should be when we get barely enough $(e,d)$ pairs to hope find one allowing success.
perhaps, if a large composite remains that needs to be factored, MPQS or GNFS.


Illustration, based on the the 829-bit RSA-250 recently factored.
We get $e=65537$ and the following 828-bit $d$ known to be $d=e^{-1}\bmod\varphi(n)$.
1219002363472329316632678572665837077877528004905520939230037996503041169769564562618818603930146413036298872224725717654149810234132887053185714832075764978825457518728410705223332728199047961645304133836997233492855592278022423674340390891560261753

We compute the 844-bit $m=e\,d-1$, and pull out its smalls factor $2^3\times3\times5\times13\times6221\times6213239\times440117350342384303$ (that's seconds), leaving a 740-bit $m_1$ to factor.
The command¹ ecm -pm1 1e7 &lt;m1 found a 73-bit factor $8015381692860102796237$ in &lt;3s, leaving a 667-bit $m_2$ to factor.
The command ecm -pp1 1e7 &lt;m2 found a 67-bit factor $101910617047160921359$ in &lt;7s, leaving a 600-bit $m_3$ to factor.
The command ecm -pp1 1e8 &lt;m3 found a 72-bit factor $4597395223158209096147$ in &lt;77s, leaving a 528-bit $m_4$ to factor.
We need to factor that $m_4$, because it is still too large to be a divisor of $p-1$ or $q-1$. The command ecm -pm1 3e8 &lt;m4 failed after ≈85s. The command ecm -pp1 1e8 &lt;m4 failed after ≈69s. The command ecm 1e8 &lt;m4 launched repeatedly on multiple cores repeatedly failed after ≈272s. We would have been very lucky if that had worked.
I did not really factor $m_4$ with GNFS², but that's well within reach. The factors of $m_4$ are  276-bit and 253-bit (the first two in the list below)
$p-1$ and $q-1$ are even, thus we have these 12 factors to split between $(p-1)/2$, $(q-1)/2$ and $h$:
72769022935390028131583224155323574786067394416649454368282707661426220155269516297
11015842872223957032465527015746975907581857223611379316467045416408679146689
8015381692860102796237
4597395223158209096147
101910617047160921359
440117350342384303
6213239
6221
13
5
3
2

There are a mere $3^{10}&lt;2^{16}$ possibilities to explore after we assigned the first two entries to $(p-1)/2$ and $(q-1)/2$. We want to explore those with $\max(p,q)&lt;2\min(p,q)$ and $h&lt;e$. Pruning this tree requires only addition of approximate logarithms. That's a near-trivial knapsack problem. I've not coded it, but I'd be surprised if there was a solution yielding $p$ and $q$ prime other than $h=2\times3\times6221$, and these $p$ and $q$ which immediately yields $n=p\,q$, here RSA-250.
33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367


¹ GMP-ECM implements carefully optimized Pollard's p-1, William's p+1, and ECM. I let it use a random seed, thus some of the results may take a few runs to reproduce.
² I'm hearing a lot of good of the implementation in CADO-NFS.