On inverses of some permutation polynomials over finite fields of characteristic three

Yanbin Zheng, Fu Wang, Libo Wang, Wenhong WeiFinite Fields Their Appl 2020 · DOI

TL;DR

This paper tackles the challenging problem of finding explicit formulas for the inverses of certain types of permutation polynomials (PPs) over finite fields of characteristic three. By developing a novel combination of piecewise methods and interpolation techniques, the authors successfully determine these inverses for specific classes of reversed Dickson and generalized cyclotomic mapping PPs, contributing valuable tools for finite field arithmetic and cryptography.

What Problem Does This Paper Address?

Permutation polynomials (PPs) are crucial in finite field theory, particularly for constructing error-correcting codes and cryptographic systems. A PP of a finite field $F_q$ is a polynomial that permutes the elements of the field. For a PP $f(x)$, its inverse $f^{-1}(x)$ is another polynomial such that $f^{-1}(f(x)) = x$. While the existence of such an inverse is guaranteed, finding an explicit, closed-form expression for it is often a difficult task, especially for PPs with complex structures. This paper focuses on a specific characteristic, characteristic three ($F_3$), and addresses the problem of finding explicit inverses for two important families of PPs: reversed Dickson polynomials and generalized cyclotomic mapping polynomials. These PPs have applications in various areas, but their inverses have remained elusive, hindering their full utilization.

Methods

The authors employ a multi-pronged approach, combining several established techniques with novel adaptations:

  • Piecewise Method: This method, previously used for constructing PPs and their inverses, involves breaking down the polynomial into pieces defined on different subsets of the finite field. The paper extends this by carefully defining these subsets ($C_0$ and $C_1$) based on quadratic residues in $F_{3^n}$.
  • Lagrange Interpolation Formula: This standard technique is used to reconstruct polynomials from their values on a set of points. The paper leverages it to express the inverse polynomial based on its behavior on the defined subsets.
  • Lucas' Theorem: This theorem provides a way to compute binomial coefficients modulo a prime. It is crucial for simplifying and evaluating the coefficients that arise in the inverse polynomial formulas, particularly in characteristic three.
  • Novel Combinations and Adaptations: The core innovation lies in the strategic combination of these methods. The authors develop a general framework (Theorem 2) for finding the inverse of a piecewise PP by relating the coefficients of the inverse to specific coefficients of the original polynomial's pieces. This framework is then applied to the specific forms of reversed Dickson and generalized cyclotomic mapping polynomials. They also introduce specific lemmas and theorems to handle the intricacies of characteristic three arithmetic and binomial coefficient calculations.

Datasets

Not discussed in the paper. The paper deals with theoretical constructions and explicit formulas over finite fields, not empirical evaluation on datasets.

Key Insights and Ideas

  • Decomposition is Key: The paper highlights the power of decomposing complex PPs into simpler, piecewise functions defined on carefully chosen subsets of the finite field. This strategy significantly simplifies the problem of finding inverses.
  • Bridging Theory and Practice: The work provides concrete, explicit formulas for inverses, moving beyond theoretical existence proofs. This is vital for practical applications in areas like cryptography.
  • Characteristic Three Specifics: The paper demonstrates how the unique properties of arithmetic in characteristic three (e.g., $1+1+1=0$) and specific binomial coefficient congruences can be leveraged to derive elegant inverse formulas.
  • Connection to Dickson Polynomials: The paper establishes a direct link between the inverses of certain PPs and the well-studied reversed Dickson polynomials, extending existing knowledge in this area.

Key Results

The paper presents several key results:

  • Explicit Inverse Formula for Reversed Dickson PPs: Theorem 1 provides a detailed formula for the inverse of a specific class of reversed Dickson permutation polynomials of the form $f(x) = (x - x^2 - x^3)x^3$ over $F_{3^n}$ (where $n$ is even). This formula is expressed in terms of binomial coefficients.
  • General Framework for Piecewise PPs: Theorem 2 offers a general method to compute the inverse of a piecewise PP $f(x)$ over $F_q$ (where $q$ is an odd prime power $>3$), provided its pieces induce bijections between specific subsets of the field.
  • Explicit Inverse for Generalized Cyclotomic Mapping PPs: Section 5 extends the methodology to derive explicit inverses for some generalized cyclotomic mapping PPs, building upon the framework developed for Dickson polynomials.
  • Evaluation of Binomial Coefficients: Theorems 3, 4, 5, 6, and Corollaries 1 provide detailed methods and results for evaluating specific binomial coefficients modulo 3, which are essential for simplifying the inverse formulas.

Limitations and Future Work

  • Specific Classes: The paper focuses on specific classes of PPs. While the methods are generalizable, finding explicit inverses for all PPs remains an open challenge.
  • Characteristic Three: The results are specific to characteristic three. Extending these methods to other characteristics would be a valuable direction.
  • Computational Complexity: While explicit formulas are provided, their direct computation might still be computationally intensive for very large fields. Further optimization or alternative representations could be explored.
  • Applications: The paper lays the groundwork for using these PPs and their inverses in cryptographic constructions. Future work could involve exploring these applications in detail, such as designing new ciphers or codes.

Summary updated

BibTeX
@article{zheng2020inverses,
  author = {Yanbin Zheng and Fu Wang and Libo Wang and Wenhong Wei},
  title = {{On inverses of some permutation polynomials over finite fields of characteristic three}},
  journal = {Finite Fields Their Appl},
  year = {2020},
  doi = {10.1016/j.ffa.2020.101670},
}
Figure