首页 | 本学科首页   官方微博 | 高级检索  
     

一种布尔多项式的高效计算机表示
引用本文:李昕,林东岱,徐琳.一种布尔多项式的高效计算机表示[J].计算机研究与发展,2012,49(12):2568-2574.
作者姓名:李昕  林东岱  徐琳
作者单位:1. 中国矿业大学计算机科学与技术学院 江苏徐州 221008;中国科学院大学 北京100049;信息安全国家重点实验室(中国科学院软件研究所)北京100190
2. 信息安全国家重点实验室(中国科学院软件研究所)北京100190
基金项目:国家"九七三"重点基础研究发展计划基金项目,国家自然科学基金项目,中国矿业大学青年科研基金项目
摘    要:布尔方程组求解技术对于密码分析具有重要的现实意义.然而,在众多求解算法的实际计算过程中,难以抑制的空间需求增长与计算机系统有限的存储能力之间的矛盾,正是当前制约布尔方程组求解技术取得更大成果的最主要瓶颈.针对基于消项的求解算法,分析了该矛盾的产生根源,提出了解决途径,进而设计了一种全新的布尔多项式计算机表示,称之为BanYan.BanYan适用于基于首项约化的求解算法,如F4,F5,XL等算法.通过记录中间结果的生成信息而非其本身,避免算法实现陷入项数规模高速膨胀带来的巨大存储负担.与BDD和系数矩阵等基于项的传统布尔多项式表示相比,平均情况以及最坏情况下,使用BanYan表示法所需要的空间约为项数表示法的1?l(l为计算过程中产生的多项式的平均项数),从而显著提升布尔方程组求解算法的现实求解能力.

关 键 词:代数攻击  布尔多项式代表  布尔方程组求解  Grnber基  空间需求

A High Efficient Boolean Polynomial Representation
Li Xin , Lin Dongdai , Xu Lin.A High Efficient Boolean Polynomial Representation[J].Journal of Computer Research and Development,2012,49(12):2568-2574.
Authors:Li Xin  Lin Dongdai  Xu Lin
Affiliation:1(School of Computer and Sciences, China Mining University of Technology, Xuzhou, Jiangsu 221008) 2(University of Chinese Academy of Sciences, Beijing 100049) 3(State Key Laboratory of Information Security (Institute of Software, Chinese Academy of Sciences), Beijing 100190)
Abstract:
Keywords:
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号