PaperlayerView exact revision on arXiv

Source-linked AI summary

Permutation trinomials over finite fields with even characteristic

Cunsheng Ding, Longjiang Qu, Qiang Wang, Jin Yuan, Pingzhi Yuan

arXiv:1402.5734v1cs.ITmath.IT

TL;DR

Few specific classes of permutation polynomials are known, despite their applications in areas including cryptography and coding theory. This paper derives new permutation-trinomial families by studying special equations, with examples for both odd and even m.

  • Problem

    Only a small number of classes of permutation trinomials over F2^m are known, despite their potential applications.

    Source: §1 · pp. 1–2

  • Method

    The paper studies the number of solutions to special equations to obtain new permutation-trinomial classes.

    Source: §1 · p. 2

  • Results

    The paper gives a permutation trinomial for odd m > 1 and another for even m ≥ 2.

    Source: §2 · p. 2, §3 · p. 7

  • Takeaways & Limitations

    These trinomials can be used in the Maiorana-McFarland construction for bent functions whose supports yield Hadamard difference sets and binary linear codes.

    Source: §4 · p. 12

    One analyzed setting assumes r = 2m with m even.

    Source: §3 · p. 7

Abstract

from arXiv · show

Permutation polynomials have been a subject of study for a long time and have applications in many areas of science and engineering. However, only a small number of specific classes of permutation polynomials are described in the literature so far. In this paper we present a number of permutation trinomials over finite fields, which are of different forms.

1. Introduction.

The introduction motivates sparse permutation polynomials by their mathematical and practical applications, while noting that few classes of permutation trinomials over F2^m are known. It presents new classes obtained by studying special equations, with results for odd and even m.

1. Introduction.

  • Permutation polynomials with fewer terms have been linked to cryptographic applications, nonlinear functions, and cyclic-code construction.The introduction cites Dobbertin’s trinomial and pentanomial results and an example involving cyclic codes.Source: §1 · p. 1
  • Only a small number of permutation-trinomial classes over F2^m were known, motivating a search for classes with nonzero trivial coefficients.The introduction lists six previously known classes before describing the paper’s contributions.Source: §1 · p. 2
  • The paper presents new permutation-trinomial classes over F2^m by studying the number of solutions to special equations.The authors treat odd m in Section 2 and even m in Section 3.Source: §1 · p. 2

2. The case that m is odd.

For odd m, the section establishes several permutation-polynomial results over F2^m, including an explicit family for every odd m > 1 and further theorem-stated families.

  • For every odd integer m > 1, x + x^(2(m+1)/2−1) + x^(2m−2(m+1)/2+1) is a permutation polynomial over F2^m.Source: §2 · p. 2
  • For the proof’s auxiliary g, the section shows zero is its only zero and sets up uniqueness for g(x) = a at nonzero a.The zero case is reduced to x = 0 or x = 1, and g(1) = 1; the subsequent argument targets a unique nonzero solution for each nonzero a.Source: §2 · pp. 2–3
  • Theorem 2.2 states another permutation-polynomial result over F2^m for odd m > 1.The polynomial expression is not included in the supplied theorem passages.Source: §2 · p. 3
  • Theorem 2.3 states a further permutation-polynomial result over F2^m for odd m.The polynomial expression is not included in the supplied theorem passages.Source: §2 · p. 4
  • Theorem 2.4 gives a permutation polynomial over F2^m for odd positive m and follows from Theorem 2.3.The polynomial expression is not included in the supplied theorem passages.Source: §2 · p. 7

3. The case that m is even.

For even m, the section proves permutation-trinomial results over F2^m and gives a broader criterion for a theorem’s polynomial to permute F_q^m under conditions on m, q, and k.

3. The case that m is even.

  • For every even m ≥ 2, Theorem 3.2 gives a permutation trinomial over F2^m: x + x^(2^((m+2)/2)-1) + x^(2^m-2^(m/2)+1).Source: §3 · p. 7
  • The proof seeks a unique solution to f(x) = a for each target a, first treating a in the subfield and then a outside it.For the outside-subfield case, it derives a cubic equation and reduces the remaining uniqueness question to a polynomial equation over the subfield.Source: §3 · p. 8
  • For even positive m and q not divisible by 3, Lemma 3.3’s equation has only y=0 in Fqm in cases q≡1 (mod 3), or m≡2 (mod 4), q≡2 (mod 3), and exp3(k)≥exp3(qm/2 + 1).Source: §3 · pp. 9–10
  • Theorem 3.4’s polynomial permutes F_q^m if and only if m ≡ 0 (mod 4), q ≡ 1 (mod 3), or m ≡ 2 (mod 4), q ≡ 2 (mod 3), and exp3(k) ≥ exp3(q^(m/2) + 1).Here exp3(i) is the exponent of 3 in i’s canonical factorization.Source: §3 · p. 10
  • When 4 divides m, Corollary 3.5 gives a permutation polynomial by specializing Theorem 3.4 to q = 2 and k = 2, and Corollary 3.6 identifies its compositional inverse as another permutation.The supplied passages do not include the corollary polynomials’ formulas.Source: §3 · p. 11
  • For 4 | m, Corollary 3.7 states that the polynomial in its conclusion is a permutation polynomial of F_{2^m}, although the supplied excerpt omits the polynomial’s formula.Source: §3 · p. 11

4. Summary and concluding remarks.

The concluding remarks describe coding-theory and bent-function uses for the permutation trinomials. Some coding constructions are deferred to future work.

4. Summary and concluding remarks.

  • The trinomials can be used to construct binary linear codes within one framework and binary cyclic codes by another approach; the paper leaves these coding applications to future work.Source: §4 · p. 12
  • The trinomials can be used in the Maiorana-McFarland construction to obtain bent functions whose supports are Hadamard difference sets, with incidence matrices defining binary linear codes.Source: §4 · p. 12
Loading 1402.5734v1…