0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

enter image description here

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).$

$\endgroup$
1
  • $\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$
    – killertoge
    Sep 22 '21 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.