# Polynomial Inversion over Galois Field

Hello guys I am looking to calculate the Inverse of a given polynomial in Galois field I have found the little Fermat's algorithm and the Itoh-Tsujii I am getting a bit confused with both algorithm as if having a squaring and multiplication operation should a reduction modulus be used [A.A mod F(x)] and then A.[A.A mod F(x)] and so on or the modulus operation should be used at the end of the final answer [A.A.A.A....]mod F(x)

Are they applicable to polynomials basis and not normal basis ? or is this operation for the GF(2) and not the extended fields ?

Thank you

• The question seems to be whether you calculate $a^n\bmod f$ by first multiplying $a$ with itself $n$ times and then reducing the result modulo $f$ or multiplying $a$ with itself modulo $f$ (i.e. reducing after each multiplication) $n$ times. Did I get this right? – yyyyyyy Dec 8 '14 at 14:32
• Yes, Can I do that ? distribute the modulus on each operation ? since squaring a polynomial that number of times is a bit huge for a hardware implementation – user3368764 Dec 8 '14 at 14:42
• Yes, you can: both options are mathematically valid since reduction modulo $f$ is a homomorphism. – yyyyyyy Dec 8 '14 at 14:59
• Inversion (in any field) can be done with Extended Euclidean algorithm; algorithm input is field element in question and generating polynomial. – Vadym Fedyukovych Jan 5 '15 at 8:53