I don't think there is a way that doesn't involve factorization since the prime factors for a composite number could be as large as $$$10^9$$$.

Pollard Rho is typically $$$\mathcal{O}(\sqrt{\text{smallest prime factor}})$$$ though. Since the input might itself be prime, Miller Rabin to first check primality, followed by Pollard Rho if the number if composite should be sufficient.

I don't think a div-1 + div-2 D would require to solve the exact prblm that you mentioned in the blog ,probably it will require something else , observe better

You found that the equation $$$n \equiv \frac{k(k+1)}{2} \bmod k$$$ must be satisfied for a good $$$k$$$. Is this a sufficient requirement, i.e. is every $$$k$$$ satisfying this also good? Or are there other requirements for a good $$$k$$$? You should try to find sufficient conditions for a good $$$k$$$, preferrably in the form of mathematical equations, and try to find something by playing around with the equations. I can also give more specific hints if you want more help.