Groebner基与多元多次方程组的解

一、需求

1.解多元多次方程组
2.环上多项式方程的离散对数问题

二、基本定义

1.理想：

$给定环R，I是R的子环，\\如果对任意的r\in R有rI\sub I和Ir\sub I，\\则称I是R的理想。$

三、过程

对于一个复杂的多元多次多项式G0，无论是求其方程解还是求公因式（欧几里得算法），都很复杂。
我们希望找到一个简单的多项式G，它能保持G0一样的效果。
这就是G0的Groebner basis。

Groebner basis，即G是包含G0的最小理想的生成集。
我的理解是，G0的最小理想是I，G的最小理想也是I。
理想I作为一个中间桥梁，用来生成G。
本人能力有限，看书不求甚解，原理暂不考虑。

所以，求多项式G0等于0的解，就是求Groebner基等于0的解。

四、算法

N=...
PR.<x1, x2, x3> = PolynomialRing(Zmod(N))
polys = [...]
#使用x1，x2，x3变元的多项式在环PR上
for i in range(len(...)):
    polys.append((...))

g = Ideal(polys).groebner_basis()

from Crypto.Util.number import *

for gi in g:
    x = -gi(0, 0, 0)
    print(long_to_bytes(int(x)))