Given some RSA modulus $n$, can you factor $n$ if you are given $k \cdot \phi(n)$ where $k$ is also a large prime?
(Of course, you could factor $n$ if you were given $\phi(n)$ as discussed here, but that approach does not work when you cannot factor $k \cdot \phi(n)$, right? )
Yes we can factor an RSA modulus $n$ given $n$ and $k \cdot \phi(n)$, including where $k$ is a (reasonably) large prime. We just use $f\gets k \cdot \phi(n)$ instead of $f\gets e\,d-1$ in the algorithm of this answer.
The algorithm is heuristic, and I do not claim a rigorous proof of the distribution of the runtime. Also, a larger $k$ tends to make it more costly. But in practice it works fine for $k$ of size comparable to $n$.
