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

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

A new fast algorithm for constructing depressed functions

This paper presents a new fast algorithm for constructing depressed functions g based on cryptographic functions splitting idea. By splitting different selected variables using the algorithm, we can construct a system of equations after k/2」 times of function decomposition and solving the system of equations will result in the depressed functions g. The degree of the functions g solved by this algorithm is at most k/2」 such that the degree of fg is at most 「k/2]. Its computational complexity is given as O(2k/2)w+2, which is lower than the computational complexity O((2k-1)w) available when k is large. The result turns out that depressed functions g can be constructed in lower complexity.