计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2012年
12期
2568-2574
,共7页
代数攻击%布尔多项式代表%布尔方程组求解%Gr(o)nber基%空间需求
代數攻擊%佈爾多項式代錶%佈爾方程組求解%Gr(o)nber基%空間需求
대수공격%포이다항식대표%포이방정조구해%Gr(o)nber기%공간수구
布尔方程组求解技术对于密码分析具有重要的现实意义.然而,在众多求解算法的实际计算过程中,难以抑制的空间需求增长与计算机系统有限的存储能力之间的矛盾,正是当前制约布尔方程组求解技术取得更大成果的最主要瓶颈.针对基于消项的求解算法,分析了该矛盾的产生根源,提出了解决途径,进而设计了一种全新的布尔多项式计算机表示,称之为BanYan.BanYan适用于基于首项约化的求解算法,如F4,F5,XL等算法.通过记录中间结果的生成信息而非其本身,避免算法实现陷入项数规模高速膨胀带来的巨大存储负担.与BDD和系数矩阵等基于项的传统布尔多项式表示相比,平均情况以及最坏情况下,使用BanYan表示法所需要的空间约为项数表示法的1/l(l为计算过程中产生的多项式的平均项数),从而显著提升布尔方程组求解算法的现实求解能力.
佈爾方程組求解技術對于密碼分析具有重要的現實意義.然而,在衆多求解算法的實際計算過程中,難以抑製的空間需求增長與計算機繫統有限的存儲能力之間的矛盾,正是噹前製約佈爾方程組求解技術取得更大成果的最主要瓶頸.針對基于消項的求解算法,分析瞭該矛盾的產生根源,提齣瞭解決途徑,進而設計瞭一種全新的佈爾多項式計算機錶示,稱之為BanYan.BanYan適用于基于首項約化的求解算法,如F4,F5,XL等算法.通過記錄中間結果的生成信息而非其本身,避免算法實現陷入項數規模高速膨脹帶來的巨大存儲負擔.與BDD和繫數矩陣等基于項的傳統佈爾多項式錶示相比,平均情況以及最壞情況下,使用BanYan錶示法所需要的空間約為項數錶示法的1/l(l為計算過程中產生的多項式的平均項數),從而顯著提升佈爾方程組求解算法的現實求解能力.
포이방정조구해기술대우밀마분석구유중요적현실의의.연이,재음다구해산법적실제계산과정중,난이억제적공간수구증장여계산궤계통유한적존저능력지간적모순,정시당전제약포이방정조구해기술취득경대성과적최주요병경.침대기우소항적구해산법,분석료해모순적산생근원,제출료해결도경,진이설계료일충전신적포이다항식계산궤표시,칭지위BanYan.BanYan괄용우기우수항약화적구해산법,여F4,F5,XL등산법.통과기록중간결과적생성신식이비기본신,피면산법실현함입항수규모고속팽창대래적거대존저부담.여BDD화계수구진등기우항적전통포이다항식표시상비,평균정황이급최배정황하,사용BanYan표시법소수요적공간약위항수표시법적1/l(l위계산과정중산생적다항식적평균항수),종이현저제승포이방정조구해산법적현실구해능력.
