1 | def gen_matrix(p, k, n): |
---|
2 | return [random_matrix(GF(p), n, n) for i in range(k)] |
---|
3 | |
---|
4 | def m_mul_pol_naive(A, B): |
---|
5 | C = [matrix(A[0].base_ring(),A[0].nrows(),B[0].ncols()) for _ in range(len(A)+len(B)-1)] |
---|
6 | for i in range(len(A)): |
---|
7 | for j in range(len(B)): |
---|
8 | C[i+j] += A[i]*B[j] |
---|
9 | return C |
---|
10 | |
---|
11 | def m_mul_toom(A,B): |
---|
12 | m = A[0].nrows() |
---|
13 | n = B[0].ncols() |
---|
14 | l = len(A)+len(B)-1 |
---|
15 | K = A[0].base_ring() |
---|
16 | |
---|
17 | FWD = Matrix(K, l, l, [K(i**j) for i in range(l) for j in range(l)]) |
---|
18 | BCK = ~FWD |
---|
19 | |
---|
20 | AY = [sum(FWD[i,j]*A[j] for j in range(len(A))) for i in range(l)] |
---|
21 | BY = [sum(FWD[i,j]*B[j] for j in range(len(B))) for i in range(l)] |
---|
22 | |
---|
23 | Y = [AY[i]*BY[i] for i in range(l)] |
---|
24 | |
---|
25 | |
---|
26 | |
---|
27 | Y = [sum(BCK[i,j]*Y[j] for j in range(l)) for i in range(l)] |
---|
28 | |
---|
29 | |
---|
30 | return Y |
---|
31 | |
---|