中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 系统科学研究所
An improvement over the GVW algorithm for inhomogeneous polynomial systems

文献类型：期刊论文

作者Sun, Yao1; Huang, Zhenyu1; Wang, Dingkang2; Lin, Dongdai1
刊名FINITE FIELDS AND THEIR APPLICATIONS
出版日期2016-09-01
卷号41页码:174-192
关键词Grobner basis The GVW algorithm Signature-based algorithm Linear algebra Boolean polynomial ring
ISSN号1071-5797
DOI10.1016/j.ffa.2016.06.002
英文摘要The GVW algorithm provides a new framework for computing Grobner bases efficiently. If the input system is not homogeneous, some J-pairs with larger signatures but lower degrees may be rejected by GVW's criteria, and instead, GVW has to compute some J-pairs with smaller signatures but higher degrees. Consequently, degrees of polynomials appearing during the computations may unnecessarily grow up higher, and hence, the total computations become more expensive. This phenomenon happens more frequently when the coefficient field is a finite field and the field polynomials are involved in the computations. In this paper, a variant of the GVW algorithm, called M-GVW, is proposed. The concept of mutant pairs is introduced to overcome the inconveniences brought by inhomogeneous inputs. In aspects of implementations, to obtain efficient implementations of GVW/M-GVW over boolean polynomial rings, we take advantages of the famous library M4RI. We propose a new rotating swap method of adapting efficient routines in M4RI to deal with the one-direction reductions in GVW/M-GVW. Our implementations are tested with many examples from Boolean polynomial rings, and the timings show M-GVW usually performs much better than the original GVW algorithm if mutant pairs are found. (C) 2016 Elsevier Inc. All rights reserved.
资助项目National Key Basic Research Program of China[2013CB834203] ; National Natural Science Foundation of China[11301523] ; National Natural Science Foundation of China[61502485] ; Strategic Priority Research Program of the Chinese Academy of Sciences[XDA06010701] ; IEE's Research Project on Cryptography[Y4Z0061A02]
WOS研究方向Mathematics
语种英语
WOS记录号WOS:000381062900012
出版者ACADEMIC PRESS INC ELSEVIER SCIENCE
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/23472]  
专题系统科学研究所
通讯作者Huang, Zhenyu
作者单位1.Chinese Acad Sci, Inst Informat Engn, SKLOIS, Beijing 100093, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, KLMM, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714		 Sun, Yao,Huang, Zhenyu,Wang, Dingkang,et al. An improvement over the GVW algorithm for inhomogeneous polynomial systems[J]. FINITE FIELDS AND THEIR APPLICATIONS,2016,41:174-192.
APA Sun, Yao,Huang, Zhenyu,Wang, Dingkang,&Lin, Dongdai.(2016).An improvement over the GVW algorithm for inhomogeneous polynomial systems.FINITE FIELDS AND THEIR APPLICATIONS,41,174-192.
MLA Sun, Yao,et al."An improvement over the GVW algorithm for inhomogeneous polynomial systems".FINITE FIELDS AND THEIR APPLICATIONS 41(2016):174-192.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。