0
$\begingroup$

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?

$\endgroup$
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$
    – kelalaka
    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$
    – poncho
    May 23, 2022 at 11:33
  • $\begingroup$ @poncho your interpretation is better than mine. $\endgroup$
    – kelalaka
    May 23, 2022 at 11:45

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.