How hard is it to find $k = j(ed-1)$ in RSA signature

Question

In RSA signatures the below formulas come into play:

$N=rq$ where $r$ and $q$ are large primes

$ed=1 \mod{\varphi(N)}$ where $e$ is small number with no common division with $\varphi(N)$

$a=m^d \mod{n}$ where $m$ is integer representing the message and $a$ is the signature.

I wonder given $m,N$(the public key) is the task of finding some integer $k$ such that $k = j(ed-1)$ or $k = j\varphi(N)$ where $j$ is an integer. Is it as hard as factoring $N$

Answer 1

If N is odd and square-free, and if a multiple of $\lambda(n)$ or $\varphi(n)$ is known, there is a probabilistic algorithm to recover $q,r$ from $N$ (see e.g. the solutions for J. v. zur Gathen, J. Gerhard, Modern computer algebra, 2nd ed., 2003: Algorithm 18.16 in https://cosec.bit.uni-bonn.de/fileadmin/user_upload/science/mca/solutions.pdf).