This made me look at multiplicative order again and I finally found [1] what I could not find at the time, someone explicitly stating that this is a hard problem. Now it seems so obvious that I should have looked at what cryptography has to say about it that I can not imagine why I did not. Anyway, case finally closed, I got my peace of mind now.

[1] https://math.stackexchange.com/questions/837489/algorithms-f...