Rabin-Miller primality test complexity

I was thinking about the complexity of the Rabin-Miller primality test. On wikipedia I find O(k log3n), but there is no explanation. My idea was too simple. To see if n is prime, we have k attempts and with each attempt we check if first element b is 1, else we look for the -1 in the b-sequence. Here b = a^u mod n and n-1 = 2^l * u, u odd, with (b,b^2^1,b^2^2,b^2^3,...,b^2^(l-1)). So I assume worse-case scenario, we calculate all the way down to the last exponent, right before we reach the actual fermats-primetest. So if we can represent n-1 = 2^lu with u odd, then we need in total k*(n-1)/(2u) steps. By using the binary expansion of an exponent $$t$$ and repeated squaring you can compute $$x^t$$ modulo $$n$$ with $$O(\log n)$$ modulo $$n$$ multiplication operations.

And each modulo $$n$$ multiplication and division will take $$O(\log^2 n)$$ integer operations. So this makes $$O(\log^3 n)$$ integer operations.

Once you have $$x^t$$ modulo $$n,$$ then $$x^{2t},x^{4t},x^{2^st}$$ modulo $$n$$ can be obtained by $$s\leq \log_2 n$$ iterations of repeated squaring modulo $$n$$.

All the other operations are of lower complexity.

If you repeat $$k$$ times to reduce probability of error, you get $$O(k \log^3 n).$$

• I understand that by binary expansion I would need O(log n) operations to get x^n. Since we are modulo n, each multiplication costs O(log^2n), ok!. We do k attempts O(k log^3 n), ok!. But dont we do all the way to a^(n-2), since a last squaring would be fermats prime test. So it is O(k log^2 n log (n-2))? Sep 22 '21 at 21:37