二元多项式小根求解
原论文链接，建议配合一起食用，二元小根多项式主要在P404,405,406.
由于很多次写题目都要用到二元多项式小根求解，而且关于二元多项式的文章比较稀少，而且都是一元的copper，特地在本篇博客中详细探讨。
规定d >= 多项式f中的最大幂。w为多项式中的最大系数，那么可以知道在模q的多项式中，最大系数即为q。X，Y为对应小根的上界，可以人为定义。
coron的证明如下。
定义了k为shifts且足够大，这里k=2，定义了一个新的多项式s。为下文构造出的矩阵作为铺垫。
以example为例，我们知道小根x<30,x小根y<20的情况下，找到多项式的小根。我们用X，Y代换这条多项式,根据上述的proof，我们对这条多项式进行移位
按照这九种情况组成矩阵的行，k=2，所以先构成一个9行4列的矩阵。为了使这矩阵能够行规约出较小的向量，我们构造一个9*9的矩阵，与这个矩阵拼接。
论文中也有讲述如何推算出矩阵的大小，例子中k=2，d=1，那么根据对应项构造出13*9的对角矩阵
构造出相应矩阵之后，我们计算出矩阵b的埃尔米特标准型矩阵
不难发现16129 = 127^2,2048383 = 127^3,26014461 = 127^4
那么通过LLL算法，规约出来的第一个列向量，其中X，Y代换为变量构造出新的多项式
显然G（x,y)不是F（x,y）的倍数。我们通过因式分解格基规约构造的多项式，
得到了这个多项式的小根
那么k = 3呢？那么构建出了16*25的矩阵
那么对应所有移位的多项式为
以此类推，可以知道移位越多，构建的矩阵越大，格基规约的向量维数也就越大，精度更高，当然跑的也越慢。
二元如此，那么更高元的也可以由此推之。
这里贴上二元多项式求小根的代码，其中m为移位（shifts），d 为多项式中的最高幂。
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m + 1):
base = N ^ (m - i) * f ^ i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1 / factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B * monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
老韩很热心，解决了我的所有疑问，后续还有新的发现，也会在这里做简要的探讨
不得不说这吊批博客园竟然连latex command都不支持。