c++ - Miller Rabin素性检验的时间复杂度

Question

下面这个算法的时间复杂度是多少？

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;
}

最近我对素数测试产生了兴趣，并且想知道米勒拉宾的确定性版本的时间复杂度是多少。https://cp-algorithms.com/直接取的代码

我认为时间复杂度至少O(log(d))是因为 binpower 函数是O(log(e)). 该check_composite函数也运行在O(s). 但我遇到的问题是总时间复杂度。