wouldn't that just be quadratic time?
TLDR: modular arithmetic.
You may have an impression that it should be easy and takes a small number of steps. But the complexity comes from the fact that we use modular. In a normal arithmetic you know for instance that if $a < b$, then $g^a < g^b$ (for N). But in the modular arithmetic there are no such ...