一种快速构造降次函数的新算法

• 作者: 胡予濮 陈杰 韦永壮
• 来源期刊: 西安电子科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 代数攻击 计算复杂度 布尔函数 代数次数
• 年，卷（期）: 2005,（5）
• 页码范围: 790-793
• 页数: 4页
• 分类号: TN918.1
• 字数: 3887字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-2400.2005.05.029

摘要

基于密码函数分拆的思想提出了一种快速有效构造降次函数g的新算法.该算法通过每次选取不同变量进行分拆,在函数分解┌k/2」次后建立方程组,最后通过求解此方程组得到满足条件的降次函数g.新算法可以求解代数次数至多为┌k/2」的降次函数g,使得函数 f*g的代数次数至多为「k/2」.该算法计算复杂度为O(2k/2)w+2,在k较大时,小于已有算法的计算复杂度O((2k-1)w).结果表明,在很低的计算复杂度下,能快速构造出降次函数g.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡予濮	西安电子科技大学计算机网络与信息安全教育部重点实验室	176	1288	16.0	29.0
2	韦永壮	西安电子科技大学计算机网络与信息安全教育部重点实验室	9	51	4.0	7.0
3	陈杰	西安电子科技大学计算机网络与信息安全教育部重点实验室	25	136	8.0	10.0