How to find the least positive $K$ such that $N^K \equiv 1 \pmod{P}$ where $P$ is prime and $P$ doesn't divide $N$?

Question

I noticed that this $K$ is one of the divisors of $P-1$. So my solutions is looping on the divisors of $P-1$ in ascending order, till I find the first divisor $d$ where $N^d \equiv 1 \pmod{P}$. Modular exponentiation is performed in $O\left(\log_2(\text{exponent})\right)$. But this solution works in $O\left((\text{number of divisors}) \cdot \log_2(\text{exponent})\right)$. Is there any better solution?

Answer 1

You can do slightly better, the number of distinct prime divisors in place of the number of divisors.

We have the prime decomposition of $P{-}1 = \prod q_i^{\large a_i}$. And we know that $K$ divides this number so $K = \prod q_i^{\large b_i}$.

Then we can establish each $b_i$ in turn by calculating $c_{i0} = N^{\large (P-1)/q_i^{a_i}}$ and then successively raising this to the $q_i^{th}$ power, $c_{ij} = c_{i(j-1)}^{\large q_i},$ until $c_{ij}\equiv 1\bmod P$, giving $b_i = j$.

This gives us the value of $K$ because clearly since $N^K\equiv 1 \Rightarrow N^{jK} \equiv 1 \bmod P$ also but if we don't have a sufficient multiplicity of one of the prime factors of $K$ in the exponent, we cannot be dealing with a multiple of $K$.