Efficient generation of quadratic cyclotomic classes for shortest quadratic decompositions of polynomials

摘要

Nikova et al. investigated the decomposition problem of power permutations over finite fields F-2n in (Cryptogr. Commun. 11:379-384, 2019). In particular, they provided an algorithm to give a decomposition of a power permutation into quadratic power permutations. Their algorithm has a precomputation step that finds all cyclotomic classes of F-2n and then use the quadratic ones. In this paper, we provide an efficient and systematic method to generate the representatives of quadratic cyclotomic classes and hence reduce the complexity of the precomputation step drastically. We then apply our method to extend their results on shortest quadratic decompositions of x(2n-2) from 3 = n = 16 to 3 = n = 24 and correct a typo (for n = 11). We also give two explicit formulas for the time complexity of the adaptive search to understand its efficiency with respect to the parameters.