Gröbner基的简单介绍与一些参考文献

关于sage：sage是一个相当全面的数学工具（sage帮助文档），第三届红帽杯和其他大大小小比赛都有相关的sage写的题目。

红帽杯Rlated题目

这里介绍红帽杯中的Related一题，题目大致是，三个不同的明文通过RSA加密后的密文已知，公钥也已知，同时三个明文的和也已知，其实上述这些条件已经可以解出答案了，但是题目还给出了两个无关的信息，这是我觉得题目可能要混淆人的地方，总结下来，就是解答下面这个方程组：
x0+x1+x2−s≡0modNx017−c0≡0modNx117−c1≡0modNx217−c2≡0modNx_0+x_1+x_2-s \equiv 0\mod N\\ x_0^{17}-c_0 \equiv 0\mod N\\ x_1^17-c_1 \equiv 0\mod N\\ x_2^17-c_2 \equiv 0\mod N x0​+x1​+x2​−s≡0modNx017​−c0​≡0modNx11​7−c1​≡0modNx21​7−c2​≡0modN
当中x0,x1,x2x_0,x_1,x_2x0​,x1​,x2​未知，其余已知，查阅文献找到一篇名为的论文，解决这个问题的关键就是找到Groebner basis（推荐参考书籍：Ideals,varieties and algorithm），当然这个问题在sage中很好解决，只要构建一个mod N的有三个变量的多项式环，用上述的多项式构建一个Ideal（理想），然后用sage中的groebner_basis函数即可简化多项式求出x0,x1,x2x_0,x_1,x_2x0​,x1​,x2​的值，具体是怎么求得呢，是一个叫做buchberger的算法，具体参考书籍 Ideals, Varieties, and Algorithms (4th ed.) [Cox, Little & O’Shea 2015-06-14] 文中有很详细的介绍，官方writeup如下：

#!/usr/bin/sage -python
from Crypto.Util import number
from sage.all import *N = 16084923760264169099484353317952979348361855860935256157402027983349457021767614332173154044206967015252105109115289920685657394517879177103414348487477378025259589760996270909325371731433876289897874303733424115117776042592359041482059737708721396118254756778152435821692154824236881182156000806958403005506732891823555324800528934757672719379501318525189471726279397236710401497352477683714139039769105043411654493442696289499967521222951945823233371845110807469944602345293068346574630273539870116158817556523565199093874587097230314166365220290730937380983228599414137341498205967870181640370981402627360812251649
Cs = [10607235400098586699994392584841806592000660816191315008947917773605476365884572056544621466807636237415893192966935651590312237598366247520986667580174438232591692369894702423377081613821241343307094343575042030793564118302488401888197517625333923710172738913771484628557310164974384462856047065486913046647133386246976457961265115349103039946802386897315176633274295410371986422039106745216230401123542863714301114753239888820442112538285194875243192862692290859625788686421276234445677411280606266052059579743874849594812733193363406594409214632722438592376518310171297234081555028727538951934761726878443311071990L, 2665348075952836665455323350891842781938471372943896177948046901127648217780657532963063228780230203325378931053293617434754585479452556620021360669764370971665619743473463613391689402725053682169256850873752706252379747752552015341379702582040497607180172854652311649467878714425698676142212588380080361100526614423533767196749274741380258842904968147508033091819979042560336703564128279527380969385330845759998657540777339113519036552454829323666242269607225156846084705957131127720351868483375138773025602253783595007177712673092409157674720974653789039702431795168654387038080256838321255342848782705785524911705L, 4881225713895414151830685259288740981424662400248897086365166643853409947818654509692299250960938511400178276416929668757746679501254041354795468626916196040017280791985239849062273782179873724736552198083211250561192059448730545500442981534768431023858984817288359193663144417753847196868565476919041282010484259630583394963580424358743754334956833598351424515229883148081492471874232555456362089023976929766530371320876651940855297249474438564801349160584279330339012464716197806221216765180154233949297999618011342678854874769762792918534509941727751433687189532019000334342211838299512315478903418642056097679717L, 12534425973458061280573013378054836248888335198966169076118474130362704619767247747943108676623695140384169222126709673116428645230760767457471129655666350250668322899568073246541508846438634287249068036901665547893655280767196856844375628177381351311387888843222307448227990714678010579304867547658489581752103225573979257011139236972130825730306713287107974773306076630024338081124142200612113688850435053038506912906079973403207309246156198371852177700671999937121772761984895354214794816482109585409321157303512805923676416467315573673701738450569247679912197730245013539724493780184952584813891739837153776754362L]
s = 280513550110197745829890567436265496990e = 17
l = len(Cs)
PR = PolynomialRing( Zmod(N), &＃39;x&＃39;, l )
x = PR.gens()
f1 = (65537*x[0] - 66666*x[1] + 12345*x[2] - x[3])
f2 = x[0] + x[1] + x[2] - s
Fs = [f1, f2]
Fs.extend( [ (x[i]**e - Cs[i]) for i in range(l) ] )
I = Ideal(Fs)
B = I.groebner_basis()
m = &＃39;&＃39;
for b in B[:-1][::-1]:assert b.degree() == 1mi = ZZ( -b(0,0,0,0) )m += number.long_to_bytes(mi)
print m


其实，这个代码是可以简化的，如下：

#!/usr/bin/sage -python
from Crypto.Util import number
from sage.all import *N = 16084923760264169099484353317952979348361855860935256157402027983349457021767614332173154044206967015252105109115289920685657394517879177103414348487477378025259589760996270909325371731433876289897874303733424115117776042592359041482059737708721396118254756778152435821692154824236881182156000806958403005506732891823555324800528934757672719379501318525189471726279397236710401497352477683714139039769105043411654493442696289499967521222951945823233371845110807469944602345293068346574630273539870116158817556523565199093874587097230314166365220290730937380983228599414137341498205967870181640370981402627360812251649
Cs = [10607235400098586699994392584841806592000660816191315008947917773605476365884572056544621466807636237415893192966935651590312237598366247520986667580174438232591692369894702423377081613821241343307094343575042030793564118302488401888197517625333923710172738913771484628557310164974384462856047065486913046647133386246976457961265115349103039946802386897315176633274295410371986422039106745216230401123542863714301114753239888820442112538285194875243192862692290859625788686421276234445677411280606266052059579743874849594812733193363406594409214632722438592376518310171297234081555028727538951934761726878443311071990L, 2665348075952836665455323350891842781938471372943896177948046901127648217780657532963063228780230203325378931053293617434754585479452556620021360669764370971665619743473463613391689402725053682169256850873752706252379747752552015341379702582040497607180172854652311649467878714425698676142212588380080361100526614423533767196749274741380258842904968147508033091819979042560336703564128279527380969385330845759998657540777339113519036552454829323666242269607225156846084705957131127720351868483375138773025602253783595007177712673092409157674720974653789039702431795168654387038080256838321255342848782705785524911705L, 4881225713895414151830685259288740981424662400248897086365166643853409947818654509692299250960938511400178276416929668757746679501254041354795468626916196040017280791985239849062273782179873724736552198083211250561192059448730545500442981534768431023858984817288359193663144417753847196868565476919041282010484259630583394963580424358743754334956833598351424515229883148081492471874232555456362089023976929766530371320876651940855297249474438564801349160584279330339012464716197806221216765180154233949297999618011342678854874769762792918534509941727751433687189532019000334342211838299512315478903418642056097679717L, 12534425973458061280573013378054836248888335198966169076118474130362704619767247747943108676623695140384169222126709673116428645230760767457471129655666350250668322899568073246541508846438634287249068036901665547893655280767196856844375628177381351311387888843222307448227990714678010579304867547658489581752103225573979257011139236972130825730306713287107974773306076630024338081124142200612113688850435053038506912906079973403207309246156198371852177700671999937121772761984895354214794816482109585409321157303512805923676416467315573673701738450569247679912197730245013539724493780184952584813891739837153776754362L]
s = 280513550110197745829890567436265496990e = 17
l = 3
PR = PolynomialRing( Zmod(N), &＃39;x&＃39;, l )
x = PR.gens()
#f1 = (65537*x[0] - 66666*x[1] + 12345*x[2] - x[3])#其实就是这里的x[3]没必要解出来，感觉出题人就是在混淆视听
f2 = x[0] + x[1] + x[2] - s
Fs = [f2]
Fs.extend( [ (x[i]**e - Cs[i]) for i in range(l) ] )
I = Ideal(Fs)
B = I.groebner_basis()
m = &＃39;&＃39;
for b in B[::-1]:assert b.degree() == 1mi = ZZ( -b(0,0,0) )#这里的三个0代表着让x[0],x[1],x[2]都为0，比如b=x[0]+2，则b(0,0,0)会等于2m += number.long_to_bytes(mi)
print m


sage中，term（项）和monomial（单项式）是不同的的，类Polynomial中有两个函数可以分别得到leading term和leading monomial（leading的意思可以在书中找到），这里主要说明一下term是带coefficient的monomial，如term是2x22x^22x2而相应的monomial是x2x^2x2。

在sage有理数域中计算Groebner基

R.<x,y,z> = PolynomialRing(QQ,order = &＃39;deglex&＃39;)
x,y,z = R.gens()
Fs=[x*z-y**2,x**3-z**2]
I = Ideal(Fs)
B = I.groebner_basis()
#要得出线性方程的解，我们可以使用下面的代码得到簇Varieties
I.variety(QQbar)
#If we provide no argument to variety() then the default field is QQ and
#only the rational solutions will be returned.
#For more general approximations, we provide the extended field QQbar.
#参考链接[一个参考链接](http://homepages.math.uic.edu/~jan/mcs320/mcs320notes/lec28.html#groebner-bases)


上面代码的例子在Ideals,Varieties and algorithm Edition 4一书的97页出现过，在sage的PolynomialRing类中order分为:

- ``order`` -- string or:class:`~sage.rings.polynomial.term_order.TermOrder` object, e.g.,- ``&＃39;degrevlex&＃39;`` (default) -- degree reverse lexicographic= Graded Reverse Lex Order- ``&＃39;lex&＃39;`` -- lexicographic- ``&＃39;deglex&＃39;`` -- degree lexicographic = Graded Lex Order- ``TermOrder(&＃39;deglex&＃39;,3) + TermOrder(&＃39;deglex&＃39;,3)`` -- block ordering


在使用不同order的时候，得到的基是不同的

接下来简单介绍Gröbner基：

（注意：Gröbner基的名字来源于发明者Buchberger的导师的名字，有的计算机语言将其写成了Groebner basis）
在google上找到了Mike Stillman的学习笔记
在此之前，我们应该理解在现代数学上为什么定义了那么多“空间”：

来源（知乎：@qang pan）
作者：qang pan
链接：https://www.zhihu.com/question/19967778/answer/28403912
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

什么是赋范线性空间、内积空间，度量空间，希尔伯特空间 ？ 现代数学的一个特点就是以集合为研究对象，这样的好处就是可以将很多不同问题的本质抽象出来，变成同一个问题，当然这样的坏处就是描述起来比较抽象，很多人就难以理解了。既然是研究集合，每个人感兴趣的角度不同，研究的方向也就不同。为了能有效地研究集合，必须给集合赋予一些“结构”（从一些具体问题抽象出来的结构）。从数学的本质来看，最基本的集合有两类：线性空间（有线性结构的集合）、度量空间（有度量结构的集合）。对线性空间而言，主要研究集合的描述，直观地说就是如何清楚地告诉地别人这个集合是什么样子。为了描述清楚，就引入了基（相当于三维空间中的坐标系）的概念，所以对于一个线性空间来说，只要知道其基即可，集合中的元素只要知道其在给定基下的坐标即可。但线性空间中的元素没有“长度”（相当于三维空间中线段的长度），为了量化线性空间中的元素，所以又在线性空间引入特殊的“长度”，即范数。赋予了范数的线性空间即称为赋犯线性空间。但赋范线性空间中两个元素之间没有角度的概念，为了解决该问题，所以在线性空间中又引入了内积的概念。因为有度量，所以可以在度量空间、赋范线性空间以及内积空间中引入极限，但抽象空间中的极限与实数上的极限有一个很大的不同就是，极限点可能不在原来给定的集合中，所以又引入了完备的概念，完备的内积空间就称为Hilbert空间。这几个空间之间的关系是：线性空间与度量空间是两个不同的概念，没有交集。赋范线性空间就是赋予了范数的线性空间，也是度量空间（具有线性结构的度量空间）内积空间是赋范线性空间希尔伯特空间就是完备的内积空间。

图片来源：wikipedia：Space (mathematics)
域就是一种满足以下条件的集合

理想的定义：
环R的一个非空子集I ，如果对于R的两个代数运算，满足条件：对任意a,b∈I,r∈R,有a-b∈I,ra∈I，则称 I 是环R的一个左理想。类似有右理想定义。
环R的一个非空集合I，如果对于R的两个代数运算，满足条件：对任意a,b∈I,r∈R,有a-b∈I,ar∈I，则称 I 是环R的一个右理想。
环R的一个非空子集I，如果既是左理想又是右理想，称I为R的双边理想，通常简称I为R的理想。
根据以下的定理，我们知道每个Ideal都有一个generating set

Gröbner基的定义如下，在参考书中同样给出了证明，Gröbner基就是Ideal的一个generating set

参考书中首先提到了Gröbner基的两个应用，判断一个多项式是否属于当前的Gröbner基生成的理想 （即Ideal Membership problem），另一个应用就是解equations，就像上面一开始提到的CTF题目。

在Ideals一书中多是证明，并介绍了几种基本的算法，比如Buchberger算法，改进的Buchberger算法，以及F4F_4F4​算法等来计算Groebner基。

那么Groebner basis有什么其他应用呢，比如在A Tutorial on Gröbner Bases With Applications in Signals and Systems一文中，提及了在信号处理中的作用，包括控制、机器人、编码等

如何快速计算基的算法也在不断改进中，这也是一个研究方向。

吴文俊提出的机器证明方法也使用了Groebner基，理想是由有限的基生成的，那么可以将一个定理的条件作为多项式，结论也转换为多项式，那么证明结论生成的多项式在由条件多项式生成的理想中，就可以证明该定理。即将定理证明转换为理想成员判定问题。一般而言，多项式理想的基底并不唯一，Grobner基方法和吴方法可以生成满足特定条件的理想基底，因此都可以自动判定理想成员问题。因此理论上代数范畴的机器定理证明可以被完成。但是，实际中这种方法有重重困难。详情见：顾险峰：人工智能中的联结主义和符号主义、 吴文俊方法