布尔函数连续化

第33卷第5期 2004年10月 电子科技大学学报 Joum“ofUESTofChina V01．33No．5 0ct．2004 布尔函数最优连续化 洪 洁1， 范修斌2，方 刚2，路晓峰2 (1．成都电子机械高等专科学校成都61003I，2，r扣囝科学院 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 与系统科学研究院北京100080) 【摘要】针对求取sP网络结构中布尔函数最优连续化在一定情况下是一个组合优化的问题。通过概率论和 运筹学相结合的方法，将布尔函数连续化的问题转化为连续-垂I数的线性和非线性规则问题，得到了布尔函数最优 连续化函数的存在性和唯一性的证明。 关键词布尔函数；互信息；存在性j唯一性 中图分类号0224 文献标识码A C0ntinuousoptimizationofB00leanFunctions HongJiel，FallXiubin2，FangGan92，LuXiaofen92 (1．ChengduElectronmachanicalcollegeChengdu610031； 2．AcademyofMathematicsandsystemScjencelChineseAcademyofsciencesBeUing100080) Abstract’Ibseek士'orBooleancontinuousoptimizationfhnctioni11tllespne觚oorkstmeture，m cenauincaSes，isacombillationaloptimalproblem．Usillgt11emethodintegratillgprobabili够也eo巧with operationedresearchandanalysis，t11eproblemistallsfornledintotllesolutionoflilllearandnonlinear programmingofcOnt协uousf-unctions．Asresult，theproofofexistemceanduniquenessofBooleoon continuousoptimizetionfunetionisproposedin也ispaper． KeywordsBooleanfunctions；inter_information；existence；uniqueness 在离散密码学函数连续化的基础上，文献[1】给出了若干利用极大似然估计方法分析密码问题的结论， 而利用极大似然估计方法求取布尔函数的过程是非线性函数的全局极大值的求解过程。众所周知DES、AES 等密码算法大都采用SP网络迭代技术，感兴趣的读者可参阅文献【2，3]中给出的Fly算法也采用SP网络迭代 技术，并对SP网络迭代技术给出了一定的密码学分析。而若利用文献[1]中给出的极大似然估计方法对sP网 络迭代技术进行相关的密码学分析，必须对SP网络迭代技术中所使用的布尔函数进行连续化处理。 一般来说，同一个布尔函数存在多个不同的连续化函数，而不同形式的连续化函数在将组合优化问题 转化为非线性连续最优化问题时对信息提取能力、对非线性规划问题的求解性质有很大的影响。故此时对 布尔函数的连续化方法提出了要求，需要信息提取能力强的布尔-函数的连续化方法。 布尔函数最优连续化的提出 定义1设F是一定义域为[0，1]”，值域为[0，1]上的即元连续函数，厂是一，?元布尔函数，若F的定 义域由[0，1]“限制在{0，1)”，值域由[0，1]限制在{0，1)时，即为厂函数，则称F函数是布尔函数厂的一个连续 化函数。显然布尔函数存在多种连续化函数。 例1 对于布尔函数厂(x，y)=xoy，有6个函数F(x，y)，(f_1，2，⋯，6)为厂的连续化函数： 收稿日期：2004—06—23 作者简介：洪洁(1968一)，女，在职硕士生。主要从事网络安全方面的研究 万方数据 622 电子科技大学学报 第33卷 1) E(x，y)=x+y一2砂；2)E(z，)，)=寺一去卜+少一1I+寺卜一yf；3)E(x，y)=(x—y)2； 4) 曩(x，y)=k—yl；5)E(x，y)=1一(x+y一1)2：6)坑(x，y)=1一lx+y一1l。 直接验证可得知上述六种连续化函数，当定义域由【0，1】”限制在{0，1)”，值域由[O，1】限制在{0，1)时，都 为布尔函数厂(x，y)=xoy，因此满足定义1。 引理1 设F和G都是布尔函数厂的连续化函数，则对任意五∈[0，1】，户=舻+(1一允)G，也是厂的 连续化函数。 证明因为F和G都是刀元布尔函数厂的连续化函数，所以根据定义1，V口∈刀，则F@)=G(口)= 厂@)。户@)=灯@)+(1一DG@)=(A+1一句厂@)=厂@)，故命题成立。 由引理得知同一个布尔函数的不同的连续化函数的凸组合仍然是一个连续化函数。在例1中 E(x，力=去只(x，y)+去E(x，y)，巴(x，力=去只(x，力+去兄(x，y)，即E(x，力是只(x，y)与E(z，力的凸组 合：E(x，y)是只(x，y)与圪(x，y)凸组合。从以上的分析得知，对任意的布尔函数，存在许多不同的连续 化函数。哪个是密码学意义下最优的连续化函数?在SP网络多层迭代的连续化处理过程中，得到的中间结 果应与层函数的输入变量分布律一致，才能具有优化的信息提取能力。为此，给出如下定义： 定义2设F(x。，x：，⋯，x。)是”元布尔函数厂(x，，x：，⋯，x。)的一连续化函数，若满足：P(厂(xl，．一，x。)= 1)；F(p1，．一，p，，)，其中，p，=P(x，=1)，并且x。，⋯，x。是相互独立的二元随机变量，则称 F0，，石：，⋯，x。)是胛元布尔函数／@，，x：，⋯，x。)密码学意义下的最优连续化函数。以信息论的观点分析定 义2的合理性。 引理2【41设x。，彳：，⋯，x。是取值于E且分布律分别为p，=尸(x，=1)，f_1，2，⋯，，?的随机变量，并且 x1，．一，x。是相互独立，厂(x1，x2，⋯，x，，)为任一n元布尔函数，Jr=厂(x1，X2，⋯，x。)是由彳．，x2，⋯，x，，以 及厂(x。，x：，⋯，x。)诱导出的二元随机变量，则x。，X：，⋯，x。与】厂的互信息为 砸墨，五，⋯，以)；】，)： ∑ ∑p(五吃⋯％，y)log：考坚童黑 (1) (q靶⋯h)6霉y‘也 ∥L^l工2⋯工”，∥LyJ 由引理2可以看出：当厂@．，z：，⋯，x。)的连续化函数，@，，x：，⋯，x。)满足定义2时，即 I尸(】，=1)=P(厂(x1，⋯，x。)=1)兰F(p1，⋯，p。)， ，。 l尸(】，=o)=PU(xl，⋯，瓦)=o)兰1一F(pl，⋯，p。) 、。 式中 利用F(一，x：，⋯，x。)代替厂(x。，x：，⋯，x。)，满足X。，X：，⋯，X。与】，的互信息量。故定义2中的连续化 函数是信息论意义下最优的连续化函数。 2布尔函数最优连续化函数的存在性与唯一性 定理1对于任一心元布尔函数厂(一，⋯，x。)其最优连续化函数是存在且唯一的。 证明 由定义2，令P(厂(z1，．一，X，，)=1)=日(p。，⋯，p，，)，即f∈【O，1】，f_1，2，⋯，聆．即日是关于p，，f= 1，2，⋯，胛的刀元实函数。又由于厂@l，．”，吒)是布尔函数，故得知日是关于p，，f=1，2，⋯，刀的连续函数，从 而存在性可证。 又设P(厂(Z1，．一，X。)=1)；日，(pl，．”，p。)，由于p，的任意性，故Ⅳ=日。，唯一性得证。 例2求厂(_，x2)=x。ox：的最优连续化函数。 尸(厂(xl，x2)=1)=P(xj0X2=1)=尸(x1=1，x2=0)+尸(X1=0，x2=1)= p1(1一p2)+(1一p1)p=p1+p2～2plp2 故F“，x：)=x，+x：一2x，x：是厂“，x：)=曩ox：的最优连续化函数。同时，例2也给出了一般布尔函 数的最优连续化函数的求取方法。 (下转第626页) 万方数据 626 电子科技大学学报 第33卷 的质量；'，。，％，口∥口M分别表示物体与地球相对惯性系的速度和加速度，则存在如下关系 ，咒'’卅=帆，m口卅=^4蠢"， 即 生：丝，旦：丝， ％ m 口吖 研 对该问题，也可取与地球相连的参照系来讨论。由于地球相对于惯性系有加速度口。，，故地球参照系 是一个平动加速的非惯性系(简称地球系)。在地球上观察，物体的动量为m◇。+‰)=(肜+m)％(因 善：丝)，这也是物体地球系统的总动量。另一方面，对地球系，作用于物体地球系统的相互作用外力 yM 珑 之和等于零，但此时须考虑系统所受的惯性力。作用在物体上的惯性力为聊口¨，作用在地球上的惯性力 为尬村，这两力之和等于(M+m)％。根据式(7)，在地球参照系中可列出方程 导瞰+mh】=似+mkM Uf 上式表明：物体地球系统总动量的导数等于惯性力作用之和。在这里可看到，系统的动量变化是由于 惯性力的作用获得的，惯性力起着与外力相同的作用效果。 参考文献 【l】郭士垫．理论力学(上册)【M】．北京：人民教育出版社，1982 【2】王均能．非惯性系力学概论D咽．成都：电子科技大学出版社，1993 编辑刘文珍 (上接第622页) 3结束语 本文之所以要讨论布尔函数的连续化问题，是因为在许多密码算法的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 中，随着sP网络迭代层数的 增加，一般布尔函数的连续化函数，由于不是信息论意义之下最优的连续化函数，使得目标函数的信息衰 减太大，又加之sP网络迭代的密码学意义之一就是使明码信息迅速扩散，故一般连续化函数构造的目标函 数，其优化算法的求解能力相对较差，所以布尔函数的最优连续化的问题，己成为有待进一步讨论的问题 之一。 本文部分研究结果得到了中国科学院数学与系统科学研究院章祥荪研究员、袁亚湘研究员、刘木兰研 究员及刘德冈l【副研究员的指导与帮助，在此表示感谢。 参考文献 【1】AndelmenD．Ma】【imumlikelih00destiInation印pliedtocr)，ptaIlalysisp【D】．ADissenationSub面tcedtot11e DepamnentofElectricalEngineeringaIld廿leCorll】[Ili妣eonGraduateSttldiesofStanfbrdUniVers埘inPanial FulfilImentoftlleRequirementsformeDegreeofDoctorofPhilosophy．Stanford，1979． 【2】DaemenJ，vincentRJ．Thedesignof川ndacl口咽，NewYbrk：Springe卜V打lag，2002 [3】吕述望，范修斌，周玉洁．序列密码的设计与分析嗍．北京：中软电子出版社，2003 [4】ThomasM．Cover，JoyA．ThomaS，elementsofinfonllationmeoU【^田．ChicheSterVSA：JohnWiley&Sons，Inc．， 1991 [5】KullbackS．hlfo衄ationtheoqa11dstatisticsM．NeWYbrk：Wiley，1959 编辑刘文珍 万方数据 布尔函数最优连续化 作者： 洪洁， 范修斌， 方刚， 路晓峰 作者单位： 洪洁(成都电子机械高等专科学校,成都,610031)， 范修斌,方刚,路晓峰(中国科学院数学与 系统科学研究院,北京,100080) 刊名： 电子科技大学学报 英文刊名： JOURNAL OF UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA 年，卷(期)： 2004，33(5) 被引用次数： 0次 参考文献(5条) 1.Andelmen D Maximum likelihood estimation applied to cryptanalysisp 2.Daemen J.VincentRJ The design ofrijndael 2002 3.吕述望.范修斌.周玉洁 序列密码的设计与分析 2003 4.THOMAS M Cover, Joy A. Thomas, elements of information theory 1991 5.KULLBACK S Information theory and statistics 1959 相似文献(3条) 1.会议论文 洪洁.范修斌.方刚.路晓峰 布尔函数最优连续化准则 2004 求取SP网络结构中的布尔函数的问题在一定情况下是一个组合优化问题.将布尔函数连续化的目的在于将这类组合优化问题转化为连续函数的线性或 非线性规划问题.本文给出了一般布尔函数连续化函数的定义,从理论上分析和证明了布尔函数最优连续化函数的存在性和唯一性,并给出了最优连续化函 数的若干性质.文中还提出了布尔函数的连续化函数相对熵漏的概念,指出了它与Kullback Leibler距离之间的关系,给出了布尔函数的连续化函数是最优 连续化函数的充分必要条件.这些分析结果可以直接推广到一般离散问题的连续化分析之中. 2.期刊论文 洪洁.范修斌.方刚.路晓峰 布尔函数最优连续化函数的信息论分析 -西南师范大学学报(自然科学版) 2004,29(5) 不同形式的连续化函数在将组合优化问题转化为非线性连续最优化问题时对信息提取能力、对非线性规划问题的求解性质有很大的影响.利用信息论 原理给出了布尔函数的连续化函数相对熵漏的概念,指出了它与Kullback Leibler距离之间的关系,给出了布尔函数的连续化函数是最优连续化函数的充 分必要条件.这些分析结果可以直接推广到一般离散问题的连续化分析之中. 3.会议论文 冯登国.肖国镇 非线性组合函数的最大相关分析 1996 该文讨论了布尔函数与关于其变元的一个子集的所有布尔组合之间的最大相关性，给出了求布尔函数与关于其变元的一个子集的所有布尔组合之间 的最大相关性的一个算法，探讨了布尔函数的最大相关性和互信息之间的关系，并论述了如何利用最大相关性来分析非线性组合器。同时对平衡布尔函 数和Ｂｅｎｔ函数的最大相关性进行了深入的研究。 本文链接：http://d.g.wanfangdata.com.cn/Periodical_dzkjdxxb200405037.aspx 授权使用：西安交通大学(wfxajd)，授权号：d9a7ecc7-9d91-4bea-a0df-9dd90185e49e 下载时间：2010年8月21日