How to caculate the inverse of function $x^3$ in $\mathbb{F}_{2^n}$?, Any monomial $x^d$ is a permutation in the field $\mathbb{F}_{2^n}$ iff $gdc(d,2^{n}-1)=1$,why?
3
-
$\begingroup$ Welcome to Cryptography. $x^3$ is not a function but rather a polynomial representation of the elements of the field $\mathbb F_{2^2}$. The default way to find the inverse is using extended-gcd on the polynomials. If you only need the result, use SageMath. Is this HW question? $\endgroup$– kelalakaCommented May 23, 2022 at 10:31
-
1$\begingroup$ @kelalaka: actually, I believe that by $x^3$, he is talking about the function $F(z) = z \cdot z \cdot z$, which is well defined on any field, such as $\mathbb{Z}_{2^{n}}$. $\endgroup$– ponchoCommented May 23, 2022 at 11:33
-
$\begingroup$ @poncho your interpretation is better than mine. $\endgroup$– kelalakaCommented May 23, 2022 at 11:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The order of the multiplicative group of $\mathbb F_{2^n}$ is $2^n-1$. If 3 is coprime to $2^n-1$ then there exists $d\in [1,\ldots,2^n=1]$ such that $3d\equiv 1\pmod{2^n-1}$. We can find such a $d$ using the extended Euclidean algorithm.
The function on $\mathbb F_{2^n}$ $y\mapsto y^d$ is then the inverse of the map $x\mapsto x^3$ since for $x\in\mathbb F_{2^n}^\times$ we have $(x^3)^d=x^{3d}=x^1$ (the case $x=0$ is obvious).
This means that $x\mapsto x^3$ is bijective and hence a permutation.
In the case where $3|2^n-1$, if $x^3=y$ in $\mathbb F_{2^n}$ then so to does $(\omega x)^3=y$ and $(\omega^2 x)^3=y$ where $\omega$ is a cube root of 1 in $\mathbb F_{2^n}$. It follows that in this case the map is not injective and so not a permutation.
