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

  • $\begingroup$ 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? $\endgroup$ – yyyyyyy Dec 8 '14 at 14:32
  • $\begingroup$ 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 $\endgroup$ – user3368764 Dec 8 '14 at 14:42
  • $\begingroup$ Yes, you can: both options are mathematically valid since reduction modulo $f$ is a homomorphism. $\endgroup$ – yyyyyyy Dec 8 '14 at 14:59
  • $\begingroup$ Inversion (in any field) can be done with Extended Euclidean algorithm; algorithm input is field element in question and generating polynomial. $\endgroup$ – Vadym Fedyukovych Jan 5 '15 at 8:53

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.