Grobner基生成算法的并行.

西安交大精品论文，方便你写相关论文，是参考的好资料AbstractAbstractThe theory of Grobner Bases is one of the basis for Computer- Algebra. GrobnerBases is great significance in theory and computation. It is not only for being achievedthe existence, but the more important is to be presented feasible algorithms ofcomputing Grobner Bases. In the past years, the theory of Grobner Bases had beenfound more and more applications. In fact, theory of grobner Bases and its technologywill play a big role to solve questions, which are on the polynomials or which can beconverted into ones on the polynomials. Therefore, Grobner Bases has been widelyapplied as a kind of powerful tool in Cryptography and relevant fields. It is very low ofthe computational efficiency of basic computing grobner bases algorithms to diminishthe applications of Grobner Bases. So we propose to do parallelling based on existinggenerating algorithms to raise the efficiency of computationIn this thesis, firstly, we briefly introduce theory of Grobner Bases: basic theoryand algorithms to achieve Grobner Bases, also with application domain. Then with themainstream generating algorithms, we make analysis of these algorithms, introduce theassociative paralleling problems and the key factor influencing the algorithmsefficiency-u--to reduce the middle items, which is what we mainly focus on. In theparalleling process we use C+MPI to execute. At the beginning, Structured GaussianElimination method is used to reduce the probably existing huge sparse matrices, thenParallel Complete Gaussian Pivoting Elimination is used to reduce the middle itemsand both for improving the algorithms efficiency. Next we apply grobner Bases methodinto ZKP(Zero-knowledge Proof) for identity authority, and we propose ElectronicCash Payment System model to use parallelling ZKP identity authority system based onGrobner Bases and Part Blind Signature, Finally with analysis of its transactions coursesand security.Keyword: Grobner Bases, MPI (Message Passing Interface), Gauss EliminationZKP(Zero-Knowledge Proof)参考符号参考符号alba整除b/理想I的根理想由集合S中元素生成的子群或者理想K域理想I被理想J除的商理想多项式f的首项Ic(f多项式f的首项的系数Ip(f多项式f的首项的幂积k[x1,x2…,xn]域k上n变元x,x2,…,x的多项式环12,…由多项式f,,…,生成的理想或子模gcd最大公因子Icm最小公倍式h模G约化到hs(,g)多项式f和g的S-多项式deg(f)多项式f的次数向量(x,2…,xnGB(D理想I的Gr6bner基RGB(II的既约Gr6bner基keer表示映射φ核a( f表示多项式f的次数创新性声明秉承学校严谨的学风和优良的科学道德,本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢中所罗列的内容以外,论文中不包含其他人已经发表或撰写过的研究成果;也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处,本人承担一切相关责任。本人签名:狄鸭日期:208.【3关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件,允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后遵守此规定)本人签名:狄日期:0823导师签名:日期:27第一章绪论第一章绪论随着通讯网络特别是 INTERNET的高速发展,利用网络作为信息交流和信息处理变得越来越普遍。目前,无论是国家政府还是企业都正融入到网络通信的大潮之中,从其原来的传统经营模式向网络化模式演进。电子政务、电子商务及其它的各类电子业务将成为不可逆转的发展趋势。伴随着与日俱增的海量相关网络活动的发生,人们越来越多地将其注意的焦点投向信息安全这个问题。信息安全问题主要集中体现在以下方面:(1)身份认证——确认网络客户的真实身份;(2)信息和数据的保密性—个人或系统机密信息和数据保护;(3)信息和数据的完整性—防止不合法的数据修改(4)不可抵赖性——网络环境下行为的事后的不可抵赖(数字签名)信息安全中最核心的技术是密码技术。密码技术是研究对传送信息采取何种的变换以防止第三者对信息的窃取,因而密码技术是实现所有安全服务的重要基础。密码体制从原理上可分为两大类,即单钥体制(One- key System)和双钥体制(Two- key System)。密码技术经过几十年的发展已经趋于成熟,从应用方面来看大体分为两类:对称密码技术和非对称密码技术。非对称密码技术是支撑解决上述所涉及的四个关键方面的问题的核心。目前越来越流行的是基于PKI体系模型的解决方案。公钥密码的安全性都是基于复杂的数学难题。根据所基于的数学难题来分类,有以下三类系统目前被认为是安全和有效的:(1)大整数因子分解系统(代表性的有RSA);(2)有限域离散对数系统(代表性的有DSA);(3)有限域椭园曲线离散对数系统(ECC。在有限域上,结合 Grobner基的一些良好的性质,可以在信息安全领域中的很多方面进行有效工作,如:密钥分发、加密、解密、零知识证明、数字签名、不可否认消息认证等。而且随着相关算法的进步与完善、计算机速度的提高和计算机网络的发展 grobner基的实用价值进一步得到体现,其应用范围也进一步扩展,由于其良好的性质, Grobner基已经成为了一种进行密码分析的有力工具。其中目前 Grobner基最主要的应用之一是其可以辅助解决密码学中的多变元多项式方程系统的问题。下面我们就来回顾一下 Grobner基相关理论的发展简史。 Grobner基理论的形成经历了几十年的时间,最早可追溯到1927年 F.S. Macauly的工作,其主要工作是将全序的概念引入到由多变元多项式环中单项式全体组成的集合内,其目的是Grobner基生成算法的并行研究理想的某些不变量。随后 H Hironaka于1964年在研究奇性分解( resolution ofsingularities)时,引入了多变元多项式的除法算法。1965年奥地利数学家BrnoBuchberger使用除法算法系统地研究了域上多变元多项式环的理想生成元问题。其基本思想是在单项式的集合中引入保持单项式的乘法运算的全序,称为项序,以保证多项式相处后所得余多项式的唯一性。他引入S-多项式,使得对多项式环中的任一给定的理想,从它的一组生成元出发,可计算得到一组特殊的生成元,即 grobner基(这是 Bruno buchberger用其导师的名字命名的)。B. Buchberger最大的贡献在于使 Grobner基可以计算,可以真正求出来。自从 B Buchberger发现Grobner基( Grobner bases或 Groebner bases)至今 Grobner基已经在计算代数领域内,不论是在理论研究还是实际应用中,都已经成为了一种不可或缺的强有力的计算工具,而且被视为一种可以进行密码分析的有力工具。此后, H Grauert,G Beman, D. Lazard, L Robbiano等人又分别先后对 Grobner基理论进行了进一步深入的研究。近十几年来, Grobner基的应用研究发展迅速,这包括给出切实可行的域上的多项式环中的理想的准素分解算法,其中零维理想的准素分解的研究比较彻底我们所研究的 Grobner基是一类基于有限域F的多变元多项式环F[Ⅺ]上的非零理想的特殊基。Gr6bner基方法是求解非线性代数系统的一种非数值迭代的代数方法。其基本思想是在原非线性多项式代数系统所构成的多项式环中,通过对变量和多项式项的适当排序,对原系统进行约简,最后生成一个与原系统等价且便于直接求解的标准基( Standard bases,即 Grobner基)。B. Buchberger在其论文中有如下的关于算法描述:假定有属于有限域Ⅳ上的多变元多项式环RX]中的一个多项式有限序列F,即FFⅪ],计算一组属于有限域F上的多变元多项式环F]中的Gr6ber基G,即Gc[X],则可由多项式有限序列F和 Grobner基G生成相同的理想I。Gr6bner基方法(理论和算法)能够提供一种标准的方法,这种方法能很好的解决可以被表示成由多变元多项式集合中项的形式所构成的很多问题,这些问题包括:代数几何、交换代数和多项式理想理论,非变量理论,自动化几何定理证明,编码理论,整数程序设计,偏微分方程,超几何函数,统计学,非交换代数系统理论等。因为 grobner基拥有比其他任意多项式序列更好的特性,所以很多涉及理想I的问题,只要有 Grobner基G,即可获得GsFX],则可使得计算多项式有限序列F的过程变得简单。例如理想I的构成问题:对于任意多项式f∈X,判断是否存在关系f∈I当然 grobner基最主要的应用之一是其可以辅助解决密码学领域中的多变元多项式方程系统的问题。事实上计算相关系统的 Grobner基的工作量也是相当大的。在最坏的情况下, Grobner基的运算量呈双幂指数复杂度增长。但实际第一章绪论中许多应用 Grobner基例子都可以很快的获得结果,而且在很多的计算机系统的代数计算子系统中有一条类似于Gr6 bner bases或 GroebnerBases的指令以便用户可以较方便的进行 Grobner基的相关计算。目前已经有了一些可以较为方便的直接计算Grobner基的数学软件,如 Mathematica, Maple, Singular等(参见附录),这些软件包中含有相关程序,虽然其算法不尽相同,效率也大都不太高,但随着 Grobner基求解效率的不断提升,其良好的应用前景仍然是可以预见。因为基本的求解 Grobner基的 Buchberger算法的计算效率是很低的,因而出现了许多改进 Buchberger算法的新方法。现在主流的生成算法主要包括是F4算法和F5算法F4算法是目前一种有效的而且应用较为广泛的计算 Grobner基的方法。作为对F4算法的一种改进,F5算法避免了 Grobner基的计算中的一些冗余计算。该算法还特别加入了一些附加标准用以检测无效运算,以便减少这些运算,从而可以在一定程度上加速整个算法的实现,但其整体执行效率并不是很高。本文从介绍 Grobner基入手,首先介绍了相关的代数学知识,建立项序的概念,随后介绍了求解Gr6bner基的基本理论和基本算法及其作用域,包括多项式除法及其算法、最基本的 Buchberger算法、扩展的环上及主理想环上的相关算法等;继而从现有的求解 Grobner基的主流算法出发,先对求解算法进行分析,介绍了算法的并行相关问题及影响算法效率的关键问题一一中间项的约化,这也是我们所主要关注的地方,我们在此过程中采用C+MPI技术来进行并行处理,首先采用结构化高斯消元法对可能产生大型稀疏矩阵予以简化,而后采用并行高斯全选主元消去法对中间项进行约化,以达到提高算法实现效率的目的,最后选取一个简单的实例进行验证;最后我们将 Grobner基方法应用于零知识证明方式的身份认证,提出以采用并行的基于 Grobner基的零知识证明与部分盲签名相结合的方式进行安全电子支付的模型,并对其交易过程和安全性进行了分析。当然我们的工作还主要停留在较浅的层面上,在今后的工作中我们将进一步对其进行深入与完善并争取将其实现。由于本人的知识水平有限,文中难免有缺点和错误之处,敬请批评指正。第二章 Grobner基理论第二章 Grobner基理论Grobner基是由奥地利数学家 Bruno Buchberger首先在其博土论文中介绍的。grobner基方法是求解非线性代数系统的一种非数值迭代的代数方法。其基本思想是在原非线性多项式代数系统所构成的多项式环内,通过对变量和多项式的项的适当排序,对原系统进行约简,最后生成一个与原系统等价且便于直接求解的标准基( Standard bases,即 Grobner基)。传统的结式消元法也可以是求解符号形式非线性代数系统的代数法,但它需要高度依赖于具体问题的消元技巧,并且会产生增根,这是我们在本文中主要改进的方面之一。本章中我们讲述 Grobner基的基本理论和求 Grobner基的基本算法。首先给出建立Gr6bner基理论所必须的概念-项序,然后分别讲述域上和环上的 Grobner基及其相关的基本求解算法。21算术代数知识本节中我们将讲述 grobner基理论和应用所需的最基本的算术代数知识,但是我们并未对其作系统地介绍,而仅仅是讲述最基本的、本文所涉及的、非讲不可的内容,借此可以很快的了解 Grobner基理论本身,所以对所有文中提及的定义定理未作证明。本节中的定义及定理主要摘自参考文献[9]和[10]。因为环具有两个代数系统,其中第一种运算是交换群的运算,第二种运算是半群的运算。所以首先我们介绍幺半群( monoid),进而引出 Dickson定理。 Dickson定理是建立 Grobner基理论的基石之定义21.1(半群、幺半群)一个半群( semigroup)是指一个非空集合M和M上的满足结合律的二元运算“,”,记为(M,…),即M≠,对任何a,bEM,有abEM,亦可简记ab=ab,并对任何a,b,c∈M,有abc)=(ab)c。M中的一个元素e称为幺元素或单位元(unit),如果对于a∈M,那么都有ea=ae=a。如果半群M含有元素,则称M为幺半群( monoid)。如果对于任何a·b∈M,都有ab-ba,那么称M为交换半群。定理211( Dickson定理)交换幺半群N”中的任意一个理想都是有限生成的。在后面的研究中我们将看到,在多项式环中单项式生成理想时, Dickson引理将起到关键作用定义212(主理想环)如果环R中的每个理想都是主理想,则称R为主理想fs (principal ideal ringGrobner基生成算法的并行定义213(诺特环)如果R中的每个理想都是有限生成的,则称R为诺特环( Noetherian ring),有时亦记为 Noether环。定义214(准素理想)设I是环R中的理想。则I称为准素理想 rimary ideal),是指I≠R,和对任何x,y∈R,如果xy∈R,那么或者x∈,或者有某个正整数n使得y∈Ⅰ,即I是准素理想当且仅当R/I≠0和R/I中每个零因子都是幂零元。一般说来,理想的极小准素分解并不是唯一的。但是,在理想的极小准素分解中,属于它的素理想和素理想的个数是唯一确定的。定理212诺特环R中的每个理想都有极小准素分解。在本章中我们总设R表示含有单位元的诺特( Noether)交换环,k表示一般的域,设A=k[x,x2…,x]表示域k上的n变元多项式环,或者A=R[x,x2,…,xn]RⅨ]表示n变元多项式环。22项序Grobner基理论的本质是从多变元多项式环中任意一个理想的一组生成元出发,描述和计算出一组具有“良好”性质的生成元,而具有这种良好性质的生成元,可以帮助我们研究理想的结构和进行某些理想运算。由理想的一组生成元出发求出另一组生成元,很自然的想到,其过程必定含有多变元多项式的除法运算,或确切的说,含有一个多项式被一个非零多项式去除,或被多个非零多项式去除的运算。对于域上的单变元的情形,利用长除法便可做到。但对环上的多变元情形,问题变得复杂得多。即便是域上的情形,如果变元个数大于或等于2,按通常的办法作除法,其商多项式和余多项式都不保证唯一。而如果每次运算的结果不同,这种运算就没有多大的意义了。对于环上的情形,即便是单变元,也相当困难。我们先研究域上的多变元的情形。对域上的两个单变元多项式可以进行除法运算的关键是在于每次运算都可用消最高次项进行,而在用消元法解域上的线性方程组时,需要先确定变元的消去顺序,而后再根据高斯消去进行运算。由此在要做多变元多项式除法时,应在单项式集合或变元的幂积的集合中引进序,当然是全序。进而,由于单项式间可进行乘法运算,因此希望引进的序能够与乘法运算相容,或者说保持乘法运算。通常具有这种性质的序被称为项序。本节的主要内容就是给出项序的确切定义和基本性质。令N是非负整数集合,n是一个给定的正整数,石,x2,…,x表示环R上的n个变元。令集合T={x3,,…,x∈N,=12…,n,即俨”是n个变元x,x2…xn的幂积的集合。简记x2x23…x=Ⅹa,其中