# multiplicative inverse [duplicate]

I actually do want to know how to generate the multiplication inverse (M.I) table, I mean the calculation how the M.I been generated.. such as the M.I of 22 is 5A regarding to the table.. Do you know how to calculate M.I how the 22 will become 5A

22 is the hex encoding of a binary polynomial $$f = x^5 + x$$ that is used to represent the element of the AES finite field (the field is defined as $$F_{2^8} = GF(2)[x] / p(x)$$) where $$p(x) = x^8+x^4+x^3+x+1$$ is the reduction polynomial.

Now, we need to find the multiplicative inverse of $$f(x)$$, i.e. another polynomial $$g(x)$$ such that $$f(x)\cdot g(x) \equiv 1 \pmod{p(x)}$$ We can do this either by using extended Euclid algorithm for polynomials or using the fact that $$f^{-1}(x) = f^{254}(x)$$ because of the Little Fermat's Theorem.

Using a computational algebra package like e.g. GP/PARI we can compute

p = Mod(1,2)*x^8 + Mod(1,2)*x^4 + Mod(1,2)*x^3 + Mod(1,2)*x + Mod(1,2)
f = Mod(1,2)*x^5 + Mod(1,2)*x
g = Mod(f,p)^-1


and we get the result

Mod(Mod(1, 2)*x^6 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x, Mod(1, 2)*x^8 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2))


so we get the reduced polynomial $$x^6 + x^4 + x^3 + x$$ and this encodes as 5A, the table entry that corresponds to 22.

The only element that does not have its multiplicative inverse is 00, so by convention we define that 00 is mapped to 00 again.

• Your method is not effective to generate the table. One can fill it at most $O(n^2)$ field multiplications. – kelalaka Feb 21 at 13:49
• @kelalaka: Yes, but the question was not about efficiency of the generation algorithm (BTW. for this size of the table asymptotic complexity is just a code golf exercise) but about understanding where do these values come from. – Krystian Feb 21 at 16:38

As pointed in Krystian's comment, a former version of this answer was wrong. See correction at end of that other answer to the similar question that justified closing the present question.

• You could also call this 'an optimal technique' since you cannot go below linear complexity. One thing that bothers me though is that if we want to consider a general case, you need to find a generator of the group (i.e. how to find 02 in general?). Does it increase the complexity? – Krystian Feb 21 at 16:43
• @Kristian : you are totally right, and it happens that 02 is not a generator, thus my code does not even work! Back to the drawing board. – fgrieu Feb 21 at 16:55
• I was going to ask that. One needs to have a generator at the hand for this to work. – kelalaka Feb 21 at 17:06
• @Kristian: I hopefully got to the bottom of that, and conclude that finding the generator does not change the complexity: it is asymptotically a single field multiplication per entry in the table. See end of that answer. – fgrieu Feb 22 at 11:50