商环上模多项式的矩阵表示
前言：
看到了crew的boring_LCG，没做出来。回过头来填坑QAQ，文章来源于糖醋小鸡块师傅的blog的NSS Round 18中New Ring3，留个记录。
假设我们有商环$V={{\mathbb{Z}_p[x]}\over{\sum_0^n{v_ix^i}}}$，现在有两个多项式$a,b$，我们假设$c=ab\pmod V$
我们把他们分别记为向量形式：
$$a=(a_0,a_1,a_2,\cdots,a_{n-1})$$
$$b=(b_0,b_1,b_2,\cdots,b_{n-1})$$
$$v=(v_0,v_1,v_2,\cdots,v_{n-1},1)$$(默认模多项式为首一多项式)
$$c=(c_0,c_1,c_2,\cdots,c_{n-1})$$
我们可以把$c=ab\pmod V$分为两步：
- $d=ab$
- $c=d\ mod\ V$
我们可以知道$d$是一个最高次项为$2n-2$的多项式，所以可以得到$d$的向量表示形式$d=(d_0,d_1,d_2,\cdots,d_{2n-2})$
d=ab
因为没有模运算的参与，所以$d$中的各项次数对应的值其实就是所有$a,b$乘积能得到该次项的系数求和，表示成矩阵乘法即为：
$$ (a_0,a_1,a_2,\cdots,a_{n-1})_{1\times n}\begin{pmatrix}b_0&b_1&b_2&\cdots&b_{n-1}\\ &b_0&b_1&\cdots&b_{n-2}&b_{n-1}\\ &&b_0&\cdots&b_{n-3}&b_{n-2}&b_{n-1}\\ &&&\ddots&\vdots&\vdots&\vdots&\ddots\\ &&&&b_0&b_1&b_2&\cdots&b_{n-1}\end{pmatrix}_{n\times (2n-1)}=(d_0,d_1,d_2,\cdots,d_{2n-3},d_{2n-2})_{1\times (2n-1)} $$
$c=d\ mod\ V$
对于$d$的前$n$项(即$0$到$n-1$项)来说，因为不需要进行模运算，所以只需要将对应数值加到$c$中对应项上即可
而超过了$n-1$次的项，就要进行模运算的操作，我们可以通过构造模多项式中的同余方程来处理：
$$x^n=-(\sum_0^n{v_ix^i})\pmod{V}$$
也就是：
$$ x^{n+i}=-(v_{n-1}x^{n-1+i}+v_{n-2}x^{n-2+i}+\cdots+v_1x^{1+i}+v_0x^i)\pmod V(i\in[0,n-2]) $$
因为高次项会存在多次使用同余方程降幂，所以我们需要从$i=0$开始，把$x^{n+i}$均转化成一个次数在0~$n-1$的多项式求出系数，加到最终的多项式c的对应系数之中。
$i=0$时，实际上就是我们刚刚已经求出的式子：$$x^{n}=-(v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+\cdots+v_1x^{1}+v_0x)\pmod{V}$$
$i=1$时，会发现它又出现了需要降幂的$x^n$次方项：$$x^{n+1}=-(v_{n-1}x^n+v_{n-2}x^{n-1}+\cdots+v_1x^2+v_0x)\pmod{V}$$
我们可以想到可以通过将$i=0$的情况代入回$x^n$次方项即可继续降幂，也就得到了:$$x^{n+1}=-(v_{n-1}(-(v_{n-1}x^{n-1}+v_{n-2}x^{n-2}+\cdots+v_1x^{1}+v_0x))+v_{n-2}x^{n-1}+\cdots+v_1x^2+v_0x)\pmod{V}$$
再将其展开进行剩下的运算即可得到各项的系数。
$i=2$时，会得到：
$$x^{n+2}=-(v_{n-1}x^{n+1}+v_{n-2}x^{n}+\cdots+v_1x^3+v_0x^2)\pmod{V}$$
于是我们可以通过将$x^{n+1}$和$x^n$代入其中化简。
剩下的类似，会发现其只是一个迭代的过程，直到：
$$x^{2n+2}=-(v_{n-1}x^{2n-3}+v_{n-2}x^{2n-4}+\cdots+v_1x^{n-1}+v_0x^{n-2})\pmod{V}$$
构造矩阵只需要将大于等于$n$次方的对应展开形式中的对应项的系数，接在开始的单位矩阵下面就可得到这一步的矩阵形式。
这一部分的矩阵即为：
$$ (d_0,d_1,\cdots,d_{2n-1},d_{2n-2})_{1\times(2n-1)}\begin{pmatrix} 1\\ &1\\ &&1\\ &&&\ddots\\ &&&&1\\ poly_{n,0}&poly_{n,1}&poly_{n,2}&\cdots&poly_{n,n-1}\\ poly_{n+1,0}&poly_{n+1,1}&poly_{n+1,2}&\cdots&poly_{n+1,n-1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ poly_{2n-2,0}&poly_{2n-2,1}&poly_{2n-2,2}&\cdots&poly_{2n-2,n-1} \end{pmatrix}_{(2n-1)\times n}=(c_0,c_1,\cdots,c_{n-2},c_{n-1})_{1\times n} $$
所以最后得到矩阵应该是两步所得的矩阵的乘积：
$$ L=\begin{pmatrix}b_0&b_1&b_2&\cdots&b_{n-1}\\ &b_0&b_1&\cdots&b_{n-2}&b_{n-1}\\ &&b_0&\cdots&b_{n-3}&b_{n-2}&b_{n-1}\\ &&&\ddots&\vdots&\vdots&\vdots&\ddots\\ &&&&b_0&b_1&b_2&\cdots&b_{n-1}\end{pmatrix}_{n\times (2n-1)}\begin{pmatrix} 1\\ &1\\ &&1\\ &&&\ddots\\ &&&&1\\ poly_{n,0}&poly_{n,1}&poly_{n,2}&\cdots&poly_{n,n-1}\\ poly_{n+1,0}&poly_{n+1,1}&poly_{n+1,2}&\cdots&poly_{n+1,n-1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ poly_{2n-2,0}&poly_{2n-2,1}&poly_{2n-2,2}&\cdots&poly_{2n-2,n-1} \end{pmatrix}_{(2n-1)\times n} $$
于是我们就得到了矩阵$L$满足：
$$(a_0,a_1,\cdots,a_{n-1})L=(c_0,c_1,\cdots,c_{n-1})$$
也就是得到了我们所需要的多项式乘法的矩阵表示形式。
def poly_matrix_mul(n, v, b):
'''
将商环V上的多项式乘法a*b=c(mod v),转化成矩阵乘法,返回值为a*b=c(mod v)中的矩阵b
:param n:最高次幂
:param v:模多项式v的系数列表(从0次开始,且v必须为首一多项式)
:param b:待表示成矩阵的多项式的系数列表(从0次开始)
'''
if v[-1] != 1:
raise Exception("v must be a monic-polynomial")
mat1 = Matrix(ZZ, n, 2 * n - 1)
for i in range(n):
for j in range(n):
mat1[i, j + i] = b[j]
mat2 = Matrix(ZZ, 2 * n - 1, n)
for i in range(n):
mat2[i, i] = 1
for i in range(n, 2 * n - 1):
for j in range(i - n, n):#无需迭代展开部分
mat2[i, j] = -v[j - (i - n)]
row = vector(ZZ, n)
for j in range(i - n):#需迭代展开部分
temp = -v[n - 1 - j] * vector(ZZ, mat2[i - j - 1])
row += temp
for j in range(n):#两部分相加
mat2[i, j] += row[j]
return mat1 * mat2