0
$\begingroup$

from the paper : Cryptanalysis of a Theorem: Decomposing the Only Known Solution to the Big APN Problem (Full Version)

We represent an element $𝑥$ of $F_{2^{2𝑛}}$ as a linear polynomial $𝑥 = 𝑎𝑢 + 𝑏$ over $F_{2^𝑛}$ with multiplication modulo the irreducible polynomial $𝑢^2 + 𝑢 + 1$.

Note that $e=2^{2𝑘}+1$ and $𝑢^2 = 𝑢+1,𝑢^4 = 𝑢,...,𝑢^{2^2𝑘} = 𝑢,𝑢^{2^{2𝑘}+1} = 𝑢+1$. Then, by linearity of $𝑥 ↦ 𝑥^{𝑒−1}$

$𝑥^𝑒 =(𝑎𝑢+𝑏)^𝑒 =𝑎^𝑒𝑢^𝑒 +𝑎^{𝑒−1}𝑢^{𝑒−1}𝑏+𝑎𝑢𝑏^{𝑒−1} +𝑏^𝑒 $

$= (𝑎^𝑒 +𝑎^{𝑒−1}𝑏+𝑎𝑏^{𝑒−1})𝑢+𝑎^𝑒 +𝑏^𝑒$

$= (𝑏^𝑒 +(𝑎+𝑏)^𝑒)𝑢+𝑎^𝑒 +𝑏^𝑒$

My question is how $𝑎^𝑒𝑢^𝑒 +𝑎^{𝑒−1}𝑢^{𝑒−1}𝑏+𝑎𝑢𝑏^{𝑒−1} +𝑏^𝑒$ is derived from $(𝑎𝑢+𝑏)^𝑒$ in $F_{2^{2𝑛}}$ by pen and paper?

$\endgroup$
  • $\begingroup$ What is $e$? Something arbitrary? $\endgroup$ – Morgan Rodgers Apr 4 at 15:08
  • $\begingroup$ e=$2^{2𝑘}+ 1$ . $\endgroup$ – hardyrama Apr 4 at 15:34
  • 2
    $\begingroup$ Then since $x \mapsto x^{e-1}$ is linear, $(au+b)^e = (au+b)^{e-1}(au+b) = (a^{e-1}u^{e-1}+b^{e-1})(au+b)$. $\endgroup$ – Morgan Rodgers Apr 4 at 16:19
  • $\begingroup$ thanx for the answer $\endgroup$ – hardyrama Apr 4 at 16:30
  • 1
    $\begingroup$ Add the definition of $e$ to the question body, please. Otherwise the question is unclear. $\endgroup$ – Jyrki Lahtonen Apr 4 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.