Nilpotent linearized polynomials over finite fields and applications

Abstract

Let $q$ be a prime power and ${\mathbb{F}}_{q^n}$ be the finite field with $q^n$ elements, where $n>1$. We introduce the class of the linearized polynomials $L(x)$ over ${\mathbb{F}}_{q^n}$ such that $$L^{(t)}(x):=\underset{t\text{times}}{\underbrace{L(L(\cdots (x)\cdots ))}}\equiv 0(\mathrm{mod}{x}^{q^n}-x)$$ for some $t\ge 2$, called nilpotent linearized polynomials (NLP's). We discuss the existence and construction of NLP's and, as an application, we show how to construct permutations of ${\mathbb{F}}_{q^n}$ from these polynomials. For some of those permutations, we can explicitly give the compositional inverse map and the cycle structure. This paper also contains a method for constructing involutions over binary fields with no fixed points, which are useful in block ciphers.

arXiv comment12 pages