Ticket #12177: toom.py

def gen_matrix(p, k, n):
    return [random_matrix(GF(p), n, n) for i in range(k)]

def m_mul_pol_naive(A, B):
    C = [matrix(A[0].base_ring(),A[0].nrows(),B[0].ncols()) for _ in range(len(A)+len(B)-1)]
    for i in range(len(A)):
        for j in range(len(B)):
            C[i+j] += A[i]*B[j]
    return C

def m_mul_toom(A,B):
    m = A[0].nrows()
    n = B[0].ncols()
    l = len(A)+len(B)-1
    K = A[0].base_ring()

    FWD = Matrix(K, l, l, [K(i**j) for i in range(l) for j in range(l)])
    BCK = ~FWD

    AY = [sum(FWD[i,j]*A[j] for j in range(len(A))) for i in range(l)]
    BY = [sum(FWD[i,j]*B[j] for j in range(len(B))) for i in range(l)]

    Y = [AY[i]*BY[i] for i in range(l)]



    Y = [sum(BCK[i,j]*Y[j] for j in range(l)) for i in range(l)]


    return Y