Reference for the notations and defined objects:

Murphy and Robshaw, Essential Algebraic Structure Within the AES, page 7,8,...

First we implement the field $F=\mathbb F_2(t)$, defined by
$$ F = \mathbb F_2[T]\ /\ (T^8 + T^4 + T^3 + T + 1)\ . $$
Here, $t$ is the image of $T$ taken modulo the irreducible polynomial
$(T^8 + T^4 + T^3 + T + 1)$. This field can be simply defined in sage:

```
R.<T> = PolynomialRing( GF(2) )
RijndaelPolynomial = (T^8 + T^4 + T^3 + T + 1)
print "Is %s irreducible? %s" % ( RijndaelPolynomial, RijndaelPolynomial.is_irreducible() )
F.<t> = GF( 2**8, modulus = RijndaelPolynomial )
```

We get from the above in a further dialog with the interpreter:

```
Is T^8 + T^4 + T^3 + T + 1 irreducible? True
sage: F
Finite Field in t of size 2^8
sage: F.modulus()
x^8 + x^4 + x^3 + x + 1
sage: t.minpoly()
x^8 + x^4 + x^3 + x + 1
```

There is a more or less (humanly) canonical morphism $\psi$
$$\psi:F\to V\ ,$$
from the field $F$ to the vector space
$$ V = \mathbb F_2^8\ ,$$
with the inverse $\psi^{-1}$,
defined by making a vector
$(a_0,a_1,a_2,\dots)$ correspond to $a_0+a_1t+a_2t^2+\dots$.
This is the representation of $F$ by the forgetful functor as a vector space of dimension eight
with the (humaly chosen) basis $1,t,t^2,\dots,t^7$.

The article writes instead of $\psi:F\to V$ the programmer-like joke $\psi:GF(2^8)\to GF(2)^8$.

We now consider the following composition of maps:

(0) We start with an element $(a_0,a_1,a_2,\dots)$ of $V$, and push it into $F$, obtaining
$$w=\sum_{0\le k\le 7} a_kt^k\in F\ .$$

I will denote this map with $W=\psi^{-1}$, sorry, it is simpler to type it so.

(1) The "adjusted inverse map on F", for a non-zero $w\in F$ it is $w\to 1/w= w/w^2=w^{2^8}/w^2=w^{256}/w^2=w^{254}$.
To have a map, we formally set $0\to 0$. The formula $w\to w^{254}$ also applies for the zero element.
I will denote this map by $S$.

(2) Let $A$ be the matrix:

```
F2 = GF(2)
A = matrix( F2, 8, 8,
[ [ 1
if n-k in [-7,-6,-5,-4,0,1,2,3,4]
else 0
for k in [0..7] ]
for n in [0..7] ] )
print A
```

So this is:

```
sage: A
[1 0 0 0 1 1 1 1]
[1 1 0 0 0 1 1 1]
[1 1 1 0 0 0 1 1]
[1 1 1 1 0 0 0 1]
[1 1 1 1 1 0 0 0]
[0 1 1 1 1 1 0 0]
[0 0 1 1 1 1 1 0]
[0 0 0 1 1 1 1 1]
```

It induces a map (left multiplication by $A$) from $V$ to $V$,
where $V$ is seen as the space of column vectors with eight entries in $\mathbb F_2$.

(3) There is a further operation on $V$, namely adding `v_0`

, which is the vector corresponding to `63`

.

The composition is then a map
$$ V\to V\ ,\qquad v\to Wv\to SWv\to L_A(SWv)\to L_A(SWv)+v_0\ . $$

**Understanding $L_A$** It turns out that we have to forget now completely the "AES" box, and look only to the matrix
$A$, which does not occur explicitly or implicitly in the original post.

The linear map $L_A:V\to V$ is now moved via $\psi$ to a map from $F$ to $F$, defined by:
$$ a\to \psi^{-1}(\ L_A(\ \psi(a)\ )\ )\ . $$
Note that $0$ goes to $0$.

It turns out that there is a polynomial (function) **of a very special shape**
that "interpolates" this map, the very special shape being:
$$ f(a) = \sum_{0\le k\le 7}\lambda_k\; a^{2^k}\ . $$
From it, we associate
$$ g(a) = \sum_{0\le k\le 7}\lambda_k\; a^{255-2^k}\ . $$
The polynomial (function) $g$ differs
from $f$ by the "adjusted inverse" $S$. To still have confidence that we have a chance to guess an answer
to a question we will formulate soon, that even has a join to the posted question, note that the powers appearing in
the line

```
s = a*(y^254) + b*(y^253) + c*(y^251) + d*(y^247) + e*(y^239) + f*(y^223) + g*(y^191) + h*(y^127) + v
```

namely $254, 253, 251, 247, 239, 223, 191, 127$ are in fact:

```
sage: [ 255 - 2^k for k in [0..7] ]
[254, 253, 251, 247, 239, 223, 191, 127]
```

The add on `+ v`

comes from the operation in step (3) above.

The question is now the following one:

**How to compute the coefficients**
$$ \lambda_0, \lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5, \lambda_6, \lambda_7 $$
in $f$?

Let us compute them, and forget about any other ingredients, which are rather misleading.

(We do **not** rename them with $a,b,c,d,e,f,g,h$ so that tracing becomes difficult with the benefit of also using the letter $a$ with a different meaning.)

Because the Frobenius morphism $a\to a^2$ is a field morphism, we have first of all
$$ f(a+b) = f(a)+f(b)\ . $$
So $f$ is additive, and thus $\mathbb F_2$--linear. (As $L_A$ is, too.)

So the problem is equivalent to solving a simple linear system, $8$ equations, $8$ unknowns.
There is **no Lagrange interpolation involved**, this is just a misleading hint in a related post.
(Lagrange interpolation is something about polynomials with running degrees $0,1,2,3,\dots$ and not $1,2,4,\dots$)

The matrix of the linear system is $M$, with entries
$$ (t^n)^{2^k}\ , $$
with a row index $n$, and a columns index $k$.

The unknowns column vector has the entries $\lambda_k$.

The free vector $w$ has the components obtained from $L_A$, moved via $\psi$ to $F$, the applied on $(t^n)_n$ .

The solution is now simple:

```
F2 = GF(2)
R.<T> = PolynomialRing( F2 )
RijndaelPolynomial = (T^8 + T^4 + T^3 + T + 1)
F.<t> = GF( 2**8, modulus = RijndaelPolynomial )
A = matrix( F2, 8, 8,
[ [ 1
if n-k in [-7,-6,-5,-4,0,1,2,3,4]
else 0
for k in [0..7] ]
for n in [0..7] ] )
def psi_inverse( v ):
return sum( [ v[k]*t^k for k in [0..7] ] )
def psi( a ):
coeffs = R(a).list()
coeffs += ( [ F2(0) , ] * (8-len(coeffs)) )
return vector( F2, coeffs )
M = matrix( F, 8, 8,
[ [ (t^n)^(2^k) for k in [0..7] ]
for n in [0..7] ] )
w = matrix( F, 8, 1,
[ psi_inverse( A * psi(t^k) ) for k in [0..7] ] )
# solve M(lambda) = w
M.inverse() * w
```

This gives:

```
[ t^2 + 1]
[ t^3 + 1]
[t^7 + t^6 + t^5 + t^4 + t^3 + 1]
[ t^5 + t^2 + 1]
[ t^7 + t^6 + t^5 + t^4 + t^2]
[ 1]
[ t^7 + t^5 + t^4 + t^2 + 1]
[ t^7 + t^3 + t^2 + t + 1]
```

Note: There is maybe an improvement idea for the framework of the site - since i feel the need of a frustration karma that each user can manage herself or himself. It looks *sometimes* like cryptology is a science trying to hide mathematics and structure so far, that only hardware can understand them. Not so many papers, but many discussions that arise are then by nature cryptic. This should be considered an optimistic note, stressing out now how important a software like sage can be, without it i would have no chance to recover and understand the circle of ideas, and the phenomenological aspect from the article. Sage offers a free, structural way to think mathematically while programming, implementing stuff with compact, clean, easy readable code.

Personal note: Obviously this answer is related to the question only in a thin shake-hands, and rather by the coincidence of producing `t^2+1`

and `t^3+1`

(and the next coefficients). Strictly speaking, it should be downgraded, just following the rules of the site. This happened to me these days in a similar situation.

Please review the text for the question and make clear what is given and what should be computed.

`v, y`

given, then we build`s`

by the above formula and ask for`a,b,c,d,e,f,g,h`

? I do not think so, but it is really hard to figure out a sensible question in the given framework...Tip: don't tick the "community wiki" checkbox when posting questions.

Usually the "community wiki" tag is for questions that are not about Sage, but about Ask Sage itself.

Additionally, with the "community wiki" checkbox ticked, upvotes to the question don't earn you karma.

You need karma to be able to post links, to upvote questions and answers by others, etc.

@dan_fulea

substitution boxin the encryption cipher AES. I don't think it is necessary to know exactly what it is to understand the question.which Lagrange interpolation.@slelievre Nice tip. But how do I

untickmy question from thecommunity wiki?The question has its story in the www, notations differ from place to place, but still it is hard to get the "right framework" for the question. (For me and other answerers.)

Please understand that it is your task to make a clean, clear description of what is given and what should be computed

how.S−[2A]=E5 makes no sense.

Here is the path of the searches for related issues:

(cryptography post)[https://crypto.stackexchange.com/questions/18199/polynomial-representation-of-the-affine-part-of-the-aes-s-box]

(stackexchange post)[https://crypto.stackexchange.com/questions/18199/polynomial-representation-of-the-affine-part-of-the-aes-s-box]

(Paper by Murphy and Robshaw)[https://pdfs.semanticscholar.org/b0fe/cd3913af3a01b85c332737386bce26ac68fe.pdf]

Please give references step by step