Anzeige
Erschienen in:
14.07.2021 | Original Research
Efficient generation of quadratic cyclotomic classes for shortest quadratic decompositions of polynomials
Erschienen in: Cryptography and Communications | Ausgabe 5/2021
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.