def split(n):
    """
    Splits n into 2^s * r for an odd r; used in Miller-Rabin test for primality.
    """
    s = 0
    while (n > 0) and (n % 2 == 0):
        s += 1
        n >>= 1
    return (s,n)


def P(a,r,s,n):
    """
    Condition for primality in Miller-Rabin test.
    """
    if pow(a, r, n) == 1:
        return True
    elif (n - 1) in [pow(a, r*(2**j), n) for j in range(s)]:
        return True
    else:
        return False


def miller_rabin(n, t):
    """
    Tests n for primality t times.
    """
    (s, r) = split(n - 1)
    for i in range(t):
        a = random.randint(2, n-1)
        if not P(a, r, s, n):
            return False
    return True


def m_r_prime_gen(n):
    """
    Generates an odd that passes the Miller Rabin primality test for t = 50 in
    the interval [10^n, 10^(n + 1)]
    """
    p = 0
    while (p == 0):
        p = random.randrange(pow(10,n) + 1, pow(10, n + 1), 2)
        if not miller_rabing(p, 50):
            p = 0
    return p