Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 1-2/2017

27-05-2016

On some permutation binomials and trinomials over \(\mathbb {F}_{2^n}\)

Authors: Srimanta Bhattacharya, Sumanta Sarkar

Published in: Designs, Codes and Cryptography | Issue 1-2/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this work, we completely characterize (1) permutation binomials of the form \(x^{{{2^n -1}\over {2^t-1}}+1}+ ax \in \mathbb {F}_{2^n}[x], n = 2^st, a \in \mathbb {F}_{2^{2t}}^{*}\), and (2) permutation trinomials of the form \(x^{2^s+1}+x^{2^{s-1}+1}+\alpha x \in \mathbb {F}_{2^t}[x]\), where s, t are positive integers. The first result, which was our primary motivation, is a consequence of the second result. The second result may be of independent interest.
previous article Revisiting (nested) Roos bias in RC4 key scheduling algorithm
next article Improved elliptic curve hashing and point representation
Footnotes
1
These are polynomials of the form \(x^rf(x^{q-1\over d})\), and represent mappings of the factor group \(\mathbb {F}_{q}^{*} / C_d\) to itself, where \(C_d\) is the subgroup of \(\mathbb {F}_{q}^{*}\) of index d (see [9] for further details). We review relevant characterization results of this class of binomials in Sect. 1.2.
 
2
A polynomial \(f(x)\in \mathbb {F}_q[x]\) is called complete mapping if both f(x) and \(f(x)+x\) are PPs of \(\mathbb {F}_q\), and orthomorphism if both f(x) and \(f(x)-x\) are PPs; for even characteristic both are same. Complete mappings/orthomorphisms are useful for construction of mutually orthogonal latin squares (see [9, 26]).
 
3
The case of \(d=2\) was settled in [18]. However, it is relevant for fields of odd characteristic.
 
4
In [22, 23], the author characterized these PBs for any d in terms of Lucas sequences. However, as we have stated before, we are interested in more explicit characterization.
 
5
PBs of the form \(x^{2{q^2-1\over q-1}+1}+ax\) over \(\mathbb {F}_{q^2}\) were also characterized in the same work.
 
6
This approach was taken in [24, 26] (see also [2] and references therein).
 
7
Conditions (b) and (c) can be written together (see [25]) as the condition: \(x^rf(x)^{q-1\over d}\) permutes the set \(\{a \in \mathbb {F}_q: a^d=1\}.\)
 
Literature
1.
Akbary A., Wang Q.: On some permutation polynomials over finite fields. Int. J. Math. Math. Sci. 2005(16), 2631–2640 (2005)
2.
Akbary A., Ghioca D., Wang Q.: On constructing permutations of finite fields. Finite Fields Appl. 17(1), 51–67 (2011)
3.
Bassalygo L.A., Zinoviev V.A.: On one class of permutation polynomials over finite fields of characteristic two. In: The Ninth International Workshop on Coding and Cryptography (WCC) (2015)
4.
Bassalygo L.A., Zinoviev V.A.: Permutation and complete permutation polynomials. Finite Fields Appl. 33, 198–211 (2015)
5.
Carlitz L.: Some theorems on permutation polynomials. Bull. Am. Math. Soc. 68(2), 120–122 (1962)
6.
Charpin P., Kyureghyan G.M.: Cubic monomial bent functions: a subclass of \({\cal M}\). SIAM J. Discret. Math. 22(2), 650–665 (2008)
7.
Dickson L.E.: The analytic representation of substitutions on a power of a prime number of letters with a discussion of the linear group. Ann. Math. 11(1/6), 65–120 (1896)
8.
Ding C., Longjiang Q., Wang Q., Yuan J., Yuan P.: Permutation trinomials over finite fields with even characteristic. SIAM J. Discret. Math. 29(1), 79–92 (2015)
9.
Evans A.B.: Orthomorphism graphs of groups. Lecture Notes in Mathematics, vol. 1535. Springer, Berlin (1992)
10.
Guangkui X., Cao X.: Complete permutation polynomials over finite fields of odd characteristic. Finite Fields Appl. 31, 228–240 (2015)
11.
Hou X.-D.: Determination of a type of permutation trinomials over finite fields. II. Finite Fields Appl. 35, 16–35 (2015)
12.
Hou X.-D.: Permutation polynomials over finite fields a survey of recent advances. Finite Fields Appl. 32, 82–119 (2015)
13.
Hou X.-D.: A survey of permutation binomials and trinomials over finite fields. In: Topics in Finite Fields, Proceedings of the 11th International Conference on Finite Fields and Their Applications, vol. 632, pp. 177–191. AMS, New York (2015)
14.
Hou X.-D., Lappano S.D.: Determination of a type of permutation binomials over finite fields. J. Number Theory 147, 14–23 (2015)
15.
Lidl R., Niederreiter H.: Finite Fields, vol. 20. Cambridge University Press, Cambridge (1997)
16.
Lidl R., Wan D.: Permutation polynomials of the form \(x^rf (x^{q-1\over d})\) and their group structure. Mon. Math. 112, 149–164 (1991)
17.
Mullen G., Panario D.: Handbook of Finite Fields. CRC Press, Boca Raton (2013)
18.
Niederreiter, H., Robinson, K.H.: Complete mappings of finite fields. J. Aust. Math. Soc. (Ser. A) 33(02), 197–212 (1982)
19.
Sarkar S., Bhattacharya S., Çesmelioglu A.: On some permutation binomials of the form \(x^{{2^n-1\over k}+1}+ax\) over \(\mathbb{F}_{2^n}\): existence and count. In: Proceedings of Arithmetic of Finite Fields—4th International Workshop, Bochum, Germany, 16–19 July, 2012, pp. 236–246 (2012)
20.
Tu Z., Zeng X., Hu L.: Several classes of complete permutation polynomials. Finite Fields Appl. 25, 182–193 (2014)
21.
Wang L.: On permutation polynomials. Finite Fields Appl. 8(3), 311–322 (2002)
22.
Wang Q.: Cyclotomic mapping permutation polynomials over finite fields. In: Sequences, Subsequences, and Consequences, pp. 119–128. Springer, Berlin (2007)
23.
Wang Q.: On generalized Lucas sequences. Combinatorics and Graphs. Contemporary Mathematics, vol. 531. pp. 127–141. American Mathematical Society, Providence (2010)
24.
Wu G., Li N., Helleseth T., Zhang Y.: Some classes of monomial complete permutation polynomials over finite fields of characteristic two. Finite Fields Appl. 28, 148–165 (2014)
25.
Zieve M.: Permutation polynomials on \(\mathbb{F}_q\) induced from bijective redei functions on subgroups of the multiplicative group of \(\mathbb{F}_q\). CoRR. arXiv:​1310.​0776 (2013)
26.
Zieve M.E.: Permutation polynomials induced from permutations of subfields, and some complete sets of mutually orthogonal Latin squares. CoRR. arXiv:​1312.​1325 (2013)
Metadata
Title
On some permutation binomials and trinomials over
Authors
Srimanta Bhattacharya
Sumanta Sarkar
Publication date
27-05-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1-2/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0229-0

Other articles of this Issue 1-2/2017

Designs, Codes and Cryptography 1-2/2017 Go to the issue

OriginalPaper

Towards a general construction of recursive MDS diffusion layers

OriginalPaper

Lower bound of covering radius of binary irreducible Goppa codes

OriginalPaper

Revisiting (nested) Roos bias in RC4 key scheduling algorithm

OriginalPaper

Improving impossible-differential attacks against Rijndael-160 and Rijndael-224

OriginalPaper

On the direct construction of recursive MDS matrices

OriginalPaper

Symmetric disjunctive list-decoding codes

Premium Partner

    Image Credits