import sage.all as sg



def gen_dyadic(signature):
    n = len(signature)

    dm = [[0] * n for _ in range(n)]

    stack = []
    stack.append((n, 0, n, 0, n, 0, n))
    while stack:
        (n, i0, i1, j0, j1, k0, k1) = stack.pop()

        if n == 1:
            dm[i0][j0] = signature[k0]

        n = n/2
        if (n > 0):
            stack.append((n, i0, i0 + n, j0, j0 + n, k0, k0 + n))
            stack.append((n, i0 + n, i1, j0, j0 + n, k0 + n, k1))
            stack.append((n, i0 + n, i1, j0 + n, j1, k0, k0 + n))
            stack.append((n, i0, i0 + n, j0 + n, j1, k0 + n, k1))

        # dm[:n, :n] = gen_dyadic(signature[:n])
        # dm[n:, :n] = gen_dyadic(signature[n:])
        # dm[n:, n:] = gen_dyadic(signature[:n])
        # dm[:n, n:] = gen_dyadic(signature[n:])

    return dm

def gen_quasi_dyadic(signature):
    d1 = gen_dyadic(signature[:len(signature)/2])
    d2 = gen_dyadic(signature[len(signature)/2:])

    qd = []
    for l1, l2 in zip(d1, d2):
        qd.append(l1 + l2)

    return sg.matrix(sg.GF(2), qd)



[[1,0,0,0,0,1,0,0],
[0,1,0,0,1,0,1,0],
[0,0,1,1,0,0,0,1],
[1,0,1,1,0,0,0,0],
[0,1,0,0,1,0,0,0],
[1,0,1,0,0,1,0,0],
[0,0,0,1,0,0,1,1],
[0,0,0,0,1,0,1,1]]

a = sg.matrix(sg.GF(2),
[
[1,0,0,0,0],
[0,1,0,0,0],
[0,0,1,0,0],
[0,0,0,1,0],
[0,0,0,0,1],
])


1000100000000100
0101000000000000
0010000000000000
0101000000000000
1000100000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000