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

A new fast algorithm for constructing depressed functions

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

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（2^k/2）^w＋2 , which is lower than the computational complexity O（（2^k-1）^w） available when k is large. The result turns out that depressed functions g can be constructed in lower complexity.