def exercise4 (n, k):
        ''' Miller-Rabin procedure '''
        d = n-1
        s = 0
        while d % 2 == 0 and d != 1:
            d = d//2
            s = s + 1
     
        while k > 0:
            k = k-1;
            a = random.randint(2, n-2)
            x = a**d % n #exercise3 (a,d,n)
            if x == 1 or x == n-1:
                continue
            list = range(1,s)
            for r in list:
                x = x**2 % n
                if x == 1:
                    return "composite"
                if x == n-1:
                    continue
            return "composite"
        return "prime"