# 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$$.
If you repeat $$k$$ times to reduce probability of error, you get $$O(k \log^3 n).$$