Is the discrete log in general hard in Paillier groups?

https://en.wikipedia.org/wiki/Paillier_cryptosystem

Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily.

If I were to select $g \in \mathbb{Z}_{n^2}^*$ where $n$ divides the order of $g$, then the discrete log is easy (w.r.t base $g$) if I understand correctly.

But if I were to select any random value $r \in \mathbb{Z}_{n^2}^*$ where $n$ does not divide the order of $r$, are we then able to say anything about the difficulty of the discrete log?

I'll assume the typical Paillier set up that $n=pq$ with $p$ and $q$ prime numbers $(p-1)\not\!| q$ and vice-versa.

The recovery of a discrete logarithm $x$ of a general element $a$ with respect to a generator is equivalent to the recovery of three values: $$x\equiv\cases{x_\lambda\pmod{\lambda(n)}\\ x_p\pmod p\\ x_q\pmod q}.$$

If one knows the values of $p$ and $q$ then $x_p$ and $x_q$ are easy to recover using Fermat quotients or $p$-adic version of the logarithmic Taylor series. The best known methods to recover $x_\lambda$ rely on the number field sieve and for cryptographically sized* $p$ and $q$, this should be infeasible. If one picks a generator such that the order of the generator divides $n$, this means that $x_\lambda$ can be ignored and discrete logarithms with respect to this generator can easily be computed by anyone who knows $p$ and $q$.

In your first case where $n$ divides the order of $g$, this only tells us that $x_p$ and $x_q$ cannot be ignored. It does not ensure that $x_\lambda$ can be ignored and hence our problem could still be intractable.

In your second case where $n$ does not divide the order of $r$ this tells us that either $x_p$ can be ignored or $x_q$ can be ignored (possibly both can be ignored). It does not ensure that $x_\lambda$ can be ignored and our problem could still be intractable.

In general:

• if $p$ does not divide the order of the generator, then $x_p$ can be ignored,
• if $q$ does not divide the order of the generator, then $x_q$ can be ignored,
• if $\lambda(n)$ does not divide the order of the generator, then $x_\lambda$ can be taken ignored.

Also note that if we happen to know a bound on the size of $x$, then it may not be necessary to recover all three components. e.g. if we know that $x<pq$ then recovery of $x_p$ and $x_q$ allows us to uniquely recover $x$ from the Chinese remainder theorem.

*- Note that $p$ and $q$ have to be larger moduli than can be attacked with the number field sieve rather than simply $n$ being a larger modulus than can be attacked with the number field sieve.