混合爬山算法设计布尔函数  

Design of boolean functions using mixed hill climbing algorithms

作　　者：曹明[1] 黄银锋[1] 胡正名[1] 杨义先[1] 

机构地区：[1]北京邮电大学网络与交换技术国家重点实验室信息安全中心,北京100876

出　　处：《电子测量技术》2008年第2期1-2,6,共3页Electronic Measurement Technology

基　　金：国家自然科学基金项目(60673098);北京市自然科学基金项目(4062025)资助

摘　　要：设计高非线性度的布尔函数,具有重要的密码学意义,应用智能爬山算法能有效改善布尔函数的非线性度.分析了布尔函数真值表的单点及两点改变与Walsh-Hadamard变换之间的关系.为提高寻优时的局部特性,将HillClimb1算法和HillClimb2算法有机融合,提出了"HillClimb1+2算法",该算法将一点爬山与两点爬山交替进行,只要还有优化的可能就继续执行该算法,有效的减少陷入局部最优的可能性.实验数据表明,与基本爬山算法相比,该算法进一步优化了布尔函数的非线性度,有效提高了求解的结果。It is significant to design Boolean functions with high nonlinearity, and the nonlinearity of Boolean functions can be improved by using intelligent Hill-climbing algorithm. It is analyzed that the relationship between the Walsh- Hadamard transformation of Boolean functions and a single improvement and two points improvement. HillClimbl＋2 algorithm is proposed to improve local property of finding optimal with combining HillClimbl with HillClimb2. This algorithm is not able to stop continuing until the optimal is found, and effectively decreases the probability of getting into local optimal. Experiences show that this algorithm can improve the nonlinearity of Boolean functions.

关 键 词：布尔函数 爬山算法 非线性度 

分 类 号：TN918[电子电信—通信与信息系统]