What would be the time complexity be for this algorithm below?
using ll = long long;
using u64 = ll;
using u128 = ll;
u64 binpower(u64 base, u64 e, u64 mod) {
u64 result = 1;
base %= mod;
while (e) {
if (e & 1)
result = (u128)result * base % mod;
base = (u128)base * base % mod;
e >>= 1;
}
return result;
}
bool check_composite(u64 n, u64 a, u64 d, int s) {
u64 x = binpower(a, d, n);
if (x == 1 || x == n - 1)
return false;
for (int r = 1; r < s; r++) {
x = (u128)x * x % n;
if (x == n - 1)
return false;
}
return true;
};
bool MillerRabin(u64 n) { // returns true if n is prime, else returns false.
if (n < 2)
return false;
int r = 0;
u64 d = n - 1;
while ((d & 1) == 0) {
d >>= 1;
r++;
}
for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n == a)
return true;
if (check_composite(n, a, d, r))
return false;
}
return true;
}
Recently I have gotten interested in primality tests, and have wondered what would the time complexity be for the deterministic version of Miller-Rabin. Code directly taken by https://cp-algorithms.com/
I would think that the time complexity would be at least O(log(d))
because the binpower function is O(log(e))
. Also the check_composite
function runs in O(s)
. But the thing that I am having trouble with is the total time complexity.