论文链接😊

由于很多次写题目都要用到二元多项式小根求解，而且关于二元多项式的文章比较稀少，而且都是一元的copper，特地在本篇博客中详细探讨。

规定d>=f.degreed >=f.degree。w为多项式中的最大系数，那么可以知道在模q的多项式中，最大系数即为q。X，Y为对应小根的上界，可以人为定义。

coron的证明如下。

定义了k为shifts且足够大，这里k=2，定义了一个新的多项式s。为下文构造出的矩阵作为铺垫。

以这么example为例，我们知道小根x<30x<30,小根y<20y<20的情况下，找到多项式的小根。我们用X，YX，Y代换这条多项式,根据上述的proof，我们对这条多项式进行移位

XY⋅F(x,y)=aX2Y2+bX2Y+cXY2+dXYX⋅F(x,y)=aX2Y+BX2+cXY+dXY⋅F(x,y)=aXY2+BXY+cY2+dYF(x,y)=aXY+BX+cY+dXY\cdot F(x,y) = aX^2Y^2+bX^2Y+cXY^2+dXY\\\\ X\cdot F(x,y) = aX^2Y+BX^2+cXY+dX\\\\ Y\cdot F(x,y) = aXY^2+BXY+cY^2+dY\\\\ F(x,y) = aXY+BX+cY+d

按照这九种情况组成矩阵的行，k=2，所以先构成一个9行4列的矩阵。为了使这矩阵能够行规约出较小的向量，我们构造一个9*9的矩阵，与这个矩阵拼接。

X2Y2,X2Y,XY2,XY,X2,Y2,X,Y,1X^2Y^2,X^2Y,XY^2,XY,X^2,Y^2,X,Y,1

803300931441f3b9ea7f4d7df1b28b7

论文中也有讲述如何推算出矩阵的大小，例子中k=2，d=1，那么根据对应项构造出13*9的对角矩阵

k2+(d+k)2=13(d+k)2=9k^2+(d+k)^2 = 13\\ (d+k)^2 = 9

构造出相应矩阵之后，我们计算出矩阵b的埃尔米特标准型矩阵

0ea2d596ed657c7731587daa02f5522

不难发现16129=1272,2048383=1273,26014461=127416129 = 127^2,2048383 = 127^3,26014461 = 127^4

那么通过LLL算法，规约出来的第一个列向量，其中X，Y代换为变量构造出新的多项式

G(x,y)=−16128x2−16129y2+1048258x+983742y−28446222G(x,y) = -16128x^2 - 16129y^2+1048258x+983742y-28446222

显然G(x,y)G(x,y)不是F(x,y)F(x,y)的倍数。我们通过因式分解格基规约构造的多项式，

得到了这个多项式的小根

那么k = 3呢？那么构建出了16*25的矩阵

那么对应所有移位的多项式为

X2Y2F(x,y)=aX3Y3+bX3Y2+cX2Y3+dX2Y2X2YF(x,y)=aX3Y2+bX3Y+cX2Y2+dX2YXY2F(x,y)=aX2Y3+bX2Y2+cXY3+dXY2XY⋅F(x,y)=aX2Y2+bX2Y+cXY2+dXYX⋅F(x,y)=aX2Y+BX2+cXY+dXY⋅F(x,y)=aXY2+BXY+cY2+dYF(x,y)=aXY+BX+cY+dX^2Y^2F(x,y) =aX^3Y^3+bX^3Y^2+cX^2Y^3+dX^2Y^2\\\\ X^2YF(x,y) =aX^3Y^2+bX^3Y+cX^2Y^2+dX^2Y\\\\ XY^2F(x,y) =aX^2Y^3+bX^2Y^2+cXY^3+dXY^2\\\\ XY\cdot F(x,y) = aX^2Y^2+bX^2Y+cXY^2+dXY\\\\ X\cdot F(x,y) = aX^2Y+BX^2+cXY+dX\\\\ Y\cdot F(x,y) = aXY^2+BXY+cY^2+dY\\\\ F(x,y) = aXY+BX+cY+d

以此类推，可以知道移位越多，构建的矩阵越大，格基规约的向量维数也就越大，精度更高，当然跑的也越慢。

二元如此，那么更高元的也可以由此推之。

这里贴上二元多项式求小根的代码，其中m为移位（shifts），d 为多项式中的最高幂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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 []

老韩很热心，有问题就找他