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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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).$
-
$\begingroup$ 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))? $\endgroup$ Sep 22, 2021 at 21:37