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

Abstract

Nikova et al. investigated the decomposition problem of power permutations over finite fields $\mathbb {F}_{2^{n}}$ 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 $\mathbb {F}_{2^{n}}$ 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^{2^{n}-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.

Appendix: Interpreting the adaptive search in a different way

In this section, we give Algorithm 2 below as a different interpretation of the adaptive search in Algorithm 1. Our main purpose is to give another formulation, particularly in the form of a sum of combinations only, for the time complexity from a different perspective. As a result, we provide Theorem 3 (in addition to Theorem 1) for the time complexity of the adaptive search.

Theorem 3

• 1. Algorithm 2 gives all quadratic decompositions of x^d in the form of equation (??), with length less than or equal to t.

• 2. Let s denote the size of S in Step 1 of Algorithm 2 (which is also upper bounded by s ≤⌈n/2⌉). Then Step 2 is operated exactly

  $$ \begin{array}{@{}rcl@{}} \sum\limits_{i=1}^{s} \left( \begin{array}{c}t+i-2\\ i-1 \end{array}\right) \end{array} $$

  (4)

  times.

Proof

• 1. In Step 1, set S is constructed taking Theorem 2 into account, hence we work on a smaller subset instead of trying all possible $i=1,2,\dots ,n-1$. Also, integer 1 is inserted to S to see the existence of shorter decompositions with length less than t. In Step 2, we order all the elements of S considering their values, hence we try a decomposition only once, not unnecessarily many times.

• 2. Note that we order the exponents from the smallest to largest one in Step 2. Therefore, Step 2 resembles to the number of shortest paths problem on a grid: Construct a grid of length t − 1 and height s − 1; we want to start at a point on the left-most line, and arrive at a point on the right-most line and not above of the starting point. That means, we need to count the shortest paths from the left top corner to the right bottom corner on a i × t grid for all 1 ≤ i ≤ u, where 1 ≤ u ≤ s. For this purpose, we need to go (t − 1) times horizontally (H) and (i − 1) times vertically (V). Then, we must select the positions of H (or V) on a sequence $(H,V,H,H,V,\dots ,V)$ in which there are (i − 1) times H and (t − 1) times V. The number of repetitions of this procedure is equation (4).

□

We would like to note that the terms in the sum are linear, not multiplications of combinations.