一类布尔方程组的解

定出了一般布尔代数上方程组AX =X 的再生通解及有唯一解的充分必要条件 .同时 ,在有限布尔代数上 ,当A的每一列直交时 ,给出了AX=X 有直交解或正交解的充分必要条件 。

一类布尔方程组的可满足性阈值研究

以一类布尔方程组形式的NP问题可满足性阈值估计为研究目的,通过将高斯消去算法与摘叶算法相结合的方法给出了一种求解该问题的完全算法,并通过不同参数条件下对大量随机实例进行数值实验得到了原问题可满足性阈值的算法估计值。所得研究结果不仅首次给出了该问题的可满足性阈值估计,而且可以作为相关启发式完全算法的设计依据。

一类极大平面图4-着色布尔方程组

对极大平面图的4-着色布尔方程组F1d1(x1,x2,…,xn)=1 F2d2(x1,x2,…,xn)=1……Fndn(x1,x2,…,xn)=1进行研究,得到了该布尔方程组的5条性质,并且给出了求极大平面图4-着色全部解的一个算法.

布尔方程组解集在天气预报中的应用

通过对布尔方程组同天气预报系统对应关系的分析，指出布尔方程组是预报系统逻辑结构的具体表征。据此，预报系统在微机上运行时，可将是否符合预报系统的预报规则，转换为是否满足布尔方程的解集，从而提高预报系统在微机上的运行效率。同时，在分析布尔方程组解集布尔积因子取值规律的基础上，揭示了它同预报因子在整个预报系统中作用主次的关联，为预报因子作用主次的诊断，提供了可行的方法，并进一步提高预报系统的运行效率。

随机多比特翻转算法求解布尔多项式方程组可满足性问题

布尔多项式方程组求解问题是数学与计算机科学中的难解之一,极大布尔多项式方程组可满足性问题是一般布尔多项式方程组求解问题的扩展问题.为了解决极大布尔多项式方程组可满足性问题,首先,提出了一种可证明是否存在满足全部函数为0的解的贪婪算法,结果是不存在满足256个函数全部为0的解;其次,提出了一种基于低密度奇偶校验码,比特翻转译码算法与随机数相结合的随机多比特翻转算法.

一种布尔多项式的高效计算机表示

布尔方程组求解技术对于密码分析具有重要的现实意义.然而,在众多求解算法的实际计算过程中,难以抑制的空间需求增长与计算机系统有限的存储能力之间的矛盾,正是当前制约布尔方程组求解技术取得更大成果的最主要瓶颈.针对基于消项的求解算法,分析了该矛盾的产生根源,提出了解决途径,进而设计了一种全新的布尔多项式计算机表示,称之为BanYan.BanYan适用于基于首项约化的求解算法,如F4,F5,XL等算法.通过记录中间结果的生成信息而非其本身,避免算法实现陷入项数规模高速膨胀带来的巨大存储负担.与BDD和系数矩阵等基于项的传统布尔多项式表示相比,平均情况以及最坏情况下,使用BanYan表示法所需要的空间约为项数表示法的1?l(l为计算过程中产生的多项式的平均项数),从而显著提升布尔方程组求解算法的现实求解能力.

复合配置约束的知识审核研究

针对实例的配置合理性审核以及复合配置约束入库前的冗余和一致审核,提出了一种基于布尔方程组的复合配置约束表达形式,给出了配置约束冗余和一致判定的充分必要条件以及配置合理性审核的算法。实例表明,这种表达形式有利于对于新加入规则库的配置约束进行冗余和一致审核,并且使实例的配置合理性审核得到简化。

Randomized Stream Ciphers with Enhanced Security Based on Nonlinear Random Coding

We propose a framework for designing randomized stream ciphers with enhanced security. The key attribute of this framework is using of nonlinear bijective mappings or keyless hash functions for random coding. We investigate the computational security of the proposed ciphers against chosen-plaintext-chosen-initialization-vector attacks and show that it is based on the hardness of solving some systems of random nonlinear Boolean equations. We also provide guidelines for choosing components to design randomizers for specified ciphers.

步进的特征列算法及其在流密码分析中的应用

"吴特征列"算法是多元方程组求解的一种主要代数方法.讨论求解布尔多项式方程组特征列算法的改进算法.具体完成以下几方面工作:1)根据二阶有限域的特点,在已有工作的基础上提出布尔方程组求解的特征列算法的步进算法——SSTDCS,并且证明了该算法的正确性;2)用C语言在SzDD软件包上编程实现了该算法;3)把算法应用在流密码的代数分析中,对算法有效性进行检验,实验结果表明所给算法对大部分实例是有效与稳定的.