def _is_composite(potential_witness, exponent, factor, potential_prime):
    """
    Check if potential_prime is composite with regards to potential_witness

    For all primes p > 2, p - 1 is even and we can write that as (p - 1 == 2**e * f)
    For every value w, the following is true:
    w**f == 1 mod p
    or
    there exists an r (0 <= r <= s-1), for which w**((2**r * f) == -1 mod p

    So if we can find a witness, where this does not hold, we know the input is not prime

    :param potential_witness: The potential witness for the compositeness of the potential_prime
    :param exponent: 2**exponent * factor == potential_prime - 1
    :param factor: 2**exponent * factor == potential_prime - 1
    :param potential_prime: The potential prime to be tested
    :return: True if the potential_witness is an actual witness for the compositeness of the potential_prime
    """
    x = pow(potential_witness, factor, potential_prime)
    if x == 1 or x == potential_prime - 1:
        return False
    for i in range(exponent):
        x = pow(x, 2, potential_prime)
        if x == potential_prime - 1:
            return False
    return True