Part of the Miller-Rabin primality test in is_prime().

def check_candidate(a, d, n, s):
    """Part of the Miller-Rabin primality test in is_prime()."""
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2 ** i * d, n) == n - 1:
            return False
    return True