中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Subject: Computer Science (provided by Thomson Reuters)
Title:
一种布尔多项式的高效计算机表示
Alternative Title: a high efficient boolean polynomial representation
Author: 李昕 ; 林东岱 ; 徐琳
Keyword: 代数攻击 ; 布尔多项式代表 ; 布尔方程组求解 ; Gr(o)nber基 ; 空间需求
Source: 计算机研究与发展
Issued Date: 2012
Volume: 49, Issue:12, Pages:2568-2574
Indexed Type: EI ; WANFANG ; CNKI ; CSCD
Department: 中国矿业大学计算机科学与技术学院 江苏徐州 221008;中国科学院大学 北京100049;信息安全国家重点实验室(中国科学院软件研究所)北京100190 信息安全国家重点实验室(中国科学院软件研究所)北京100190
Sponsorship: 国家“九七三”重点基础研究发展计划基金项目(2011CB302400)|国家自然科学基金项目(60970152)|中国矿业大学青年科研基金项目(2007A039)
Abstract: 布尔方程组求解技术对于密码分析具有重要的现实意义.然而,在众多求解算法的实际计算过程中,难以抑制的空间需求增长与计算机系统有限的存储能力之间的矛盾,正是当前制约布尔方程组求解技术取得更大成果的最主要瓶颈.针对基于消项的求解算法,分析了该矛盾的产生根源,提出了解决途径,进而设计了一种全新的布尔多项式计算机表示,称之为BanYan.BanYan适用于基于首项约化的求解算法,如F4,F5,XL等算法.通过记录中间结果的生成信息而非其本身,避免算法实现陷入项数规模高速膨胀带来的巨大存储负担.与BDD和系数矩阵等基于项的传统布尔多项式表示相比,平均情况以及最坏情况下,使用BanYan表示法所需要的空间约为项数表示法的1/l(l为计算过程中产生的多项式的平均项数),从而显著提升布尔方程组求解算法的现实求解能力.
English Abstract: Solving Boolean equations for cryptanalysis has important practical significance. However, the contradiction of limited computer storage space and solving demand growth of existing algorithms is the major bottleneck for getting more progresses. This paper presents a high efficient Boolean polynomial representation, BanYan. BanYan is designed for Boolean equations solving algorithms based on leading-term eliminating, such as F4, F5, XLs. The essence of BanYan is that it only stores the information about how to generate intermediate polynomials, but not the intermediate polynomials themselves. The original polynomials in the polynomial ring for Gro¨nbner bases computation are called root polynomials. The new generated polynomials come from root polynomials by terms multiplication and polynomials addition. So we only store the corresponding terms and polynomials connected with the root polynomials. As the intermediate polynomials grow, the whole storage structure is getting just like a tree. That is why we call this method BanYan. Although the scale of intermediate polynomials grows exponentially in the process of Gro¨nbner bases computation, the generation information is becoming much more simpler, so BanYan can greatly reduce the space requirement and then improve the solving ability. Analysis and experiments show that compared with traditional representations based on terms, in average case and worst case the space requirement of BanYan has l-fold reduction. Here l is the average length of intermediate polynomials.
Language: 中文
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/15162
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:

There are no files associated with this item.


Recommended Citation:
李昕,林东岱,徐琳. 一种布尔多项式的高效计算机表示[J]. 计算机研究与发展,2012-01-01,49(12):2568-2574.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李昕]'s Articles
[林东岱]'s Articles
[徐琳]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李昕]‘s Articles
[林东岱]‘s Articles
[徐琳]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace