def StrongPrimeTest(n, t=2):
    """Tests for primitivity using a strong primitivity test. Does not guarantee primitivity."""
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    m = n - 1
    k = 0
    while m % 2 == 0:
        m //= 2
        k += 1
    b = pow(t, m, n)
    if b == 1:
        return True
    for i in range(0, k):
        if b == n - 1:
            return True
        b = b * b % n
    return False
