On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Grobner Basis Algorithms Using Linear Algebra

doi:10.1007/s11424-015-4085-1

CSpace > 系统科学研究所

	On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Grobner Basis Algorithms Using Linear Algebra
	Sun Yao 1; Huang Zhenyu 1; Lin Dongdai 1; Wang Dingkang2
	2016-06-01
发表期刊	JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY
ISSN	1009-6124
卷号	29 期号:3 页码:789-804
摘要	Some techniques using linear algebra was introduced by Faugere in F4 to speed up the reduction process during Grobner basis computations. These techniques can also be used in fast implementations of F5 and some other signature-based Grobner basis algorithms. When these techniques are applied, a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function ( given in F4). Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function, this step can be very costly when the number of involved polynomials/monomials is huge. In this paper, multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported. Many examples have been tested by using this method, and the experimental data shows that the new method is very efficient.
关键词	Boolean polynomial rings Grobner basis implementation linear algebra
DOI	10.1007/s11424-015-4085-1
语种	英语
资助项目	National Key Basic Research Program of China[2013CB834203] ; National Key Basic Research Program of China[2011CB302400] ; National Nature Science Foundation of China[11301523] ; National Nature Science Foundation of China[11371356] ; National Nature Science Foundation of China[61121062] ; Strategic Priority Research Program of the Chinese Academy of Sciences[XDA06010701] ; IEE's Research Project on Cryptography Grant[Y3Z0013102] ; IEE's Research Project on Cryptography Grant[Y3Z0018102] ; IEE's Research Project on Cryptography Grant[Y4Z0061A02]
WOS研究方向	Mathematics
WOS类目	Mathematics, Interdisciplinary Applications
WOS记录号	WOS:000379826000013
出版者	SPRINGER HEIDELBERG
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/23225
专题	系统科学研究所
通讯作者	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 100090, Peoples R China
推荐引用方式 GB/T 7714	Sun Yao,Huang Zhenyu,Lin Dongdai,et al. On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Grobner Basis Algorithms Using Linear Algebra[J]. JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,2016,29(3):789-804.
APA	Sun Yao,Huang Zhenyu,Lin Dongdai,&Wang Dingkang.(2016).On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Grobner Basis Algorithms Using Linear Algebra.JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY,29(3),789-804.
MLA	Sun Yao,et al."On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Grobner Basis Algorithms Using Linear Algebra".JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY 29.3(2016):789-804.