I want to find a linearized polynomial as my permutation polynomial in GF(2^n). I know that the only root should be 0. So, is there any way to find such polynomial instead of choosing a random one and checking the roots?
Also, how can I assess this permutation polynomial, i.e. how well it does the permutation?
TL;DR The PhD thesis linked below mentions linearized polynomials, did not dig deep to figure out the details. See also the third reference where linearized polynomial permutations are discussed.
As described on the Wikipedia page linked to in the comment by @kelalaka there are a number of families of permutation polynomials over finite fields. Let's restrict to characteristic 2, i.e., $GF(2^n):$
You ask about "assessing" the permutation. This can be in terms of its cycle structure (related to how typical the specific permutation is, with respect to pseudorandomness properties) as well as its' complexity of implementation.
One famous permutation polynomial of $GF(2^n)$ which is used in the AES Sbox for $n=8$ is $$ f(x)=x^{2^n-2}. $$ Note that it is usually written as $f(x)=x^{-1},$ for $x\neq 0,$ but since $x^{2^n-1}=1$ in $GF(2^n)$ (Lagrange's theorem) the two representations are equivalent.
As for cycle structure, a number of results are known, too detailed to go into here. See the paper linked at the bottom for some recent results. The beginning part of the linked thesis has a few examples and describes the older literature quite well.
For example, the linear polynomial $f(x)=ax+b$ is obviously the identity if $b=0,$ $a=1,$ and it is just a translation if $a=0,b\neq 0.$ In $GF(2^n)$ the translation will have cycles of length 2 since $b=-b.$
The monomial $f(x)=x^k$ is a permutation if and only if $\gcd(k,2^n-1)=1.$ Its cycle structure is fully known, Theorem 2.2 in the PhD thesis linked.
Dickson polynomials also have fully known structure, see Theorem 2.3 in the PhD thesis linked.
Linearized polynomial over $GF(2^n)$ is equivalent to a linear map $GF(2)^n \to GF(2)^n$. Permutation polynomial thus corresponds to an invertible linear map.
To answer the question: we can take a random $n\times n$ invertible binary matrix and convert it to the univariate polynomial representation. However, dealing with a concrete basis can be cumbersome. We can assume the matrix acts on the basis $\{tr(\alpha_i x)\}_i$, where $\alpha_0, \ldots, \alpha_{n-1}$ are arbitrary linearly-independent field elements, and $$ tr : GF(2^n) \to GF(2) : x \mapsto x + x^2 + x^4 + x^8 + \ldots + x^{2^{n-1}}$$ is the field trace. Then, we can simply convert the matrix columns to field elements $c_0,c_1,\ldots,c_{n-1}$ (ideally by inverting the trace-based transformation but it is not necessary since we have a random matrix) and define the final polynomial to be $$ p(x) = c_0tr(\alpha_0x) + c_1tr(\alpha_1x) + \ldots + c_{n-1}tr(\alpha_{n-1}x), $$ where the trace function can be expanded, leading to a pure linearized polynomial. It will be a permutation polynomial if and only if all $c_i$ are linearly-independent, which is guaranteed by choosing an invertible matrix.
Note: choosing coefficients in the same way directly for $x,x^2,x^4,\ldots$ does not guarantee the correctness of the map: the result may not be a permutation polynomial even if the coefficients are linearly-independent.
Here is SageMath code, it works for larger values of $n$ such as 100 ($O(n^3)$, the basis matrix can be precomputed and then getting a new poly is $O(n^2)$):
def trace(a, x):
# Sage stores polynomials as lists
# => sparse polynomials with large powers are infeasible
# return sum(x**(2**i) for i in range(n))
# replace by vector (index i => power 2**i)
return vector(a**(2**i) for i in range(n))
n = 10
F = GF(2**n, name='w')
randmat = GL(n, GF(2)).random_element().matrix()
x = PolynomialRing(F, names='x').gen()
poly = 0
for j, col in enumerate(randmat.columns()):
poly += F(col) * vector(F.fetch_int(2**j)**(2**i) for i in range(n))
print(
"poly",
" + ".join(f"({a})*x^{2**i}" for i, a in reversed(list(enumerate(poly))))
)
if n <= 10:
poly = sum(a*x**(2**i) for i, a in enumerate(poly))
assert len({poly(a) for a in F}) == len(F)
print("is permutation ok")
# poly (w^5 + w^2)*x^512 + (w^9 + w^8 + w^7 + w^6 + w^5 + w^4 + w + 1)*x^256 + (w^8 + w^5 + w^2 + 1)*x^128 + (w^5 + w^4 + w^2 + 1)*x^64 + (w^9 + w^5 + w^4 + w^3 + w^2 + w)*x^32 + (w^9 + w^5 + w^4 + 1)*x^16 + (w^9 + w^6 + w^5 + w^4 + w^2)*x^8 + (w^9 + w^8 + w^6 + w^5 + w^4 + w^2 + w + 1)*x^4 + (w^7 + w^5 + w^2 + w + 1)*x^2 + (w^9 + w^7 + w^6 + w^5 + w^4 + w^2 + 1)*x^1
# is permutation ok
PS: this approach "only" replaces the root-checking of a random linearized polynomial by the invertibility checking of a random binary matrix, which helps a lot since a standard root checking for large $n$ would be infeasible.
