0
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\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
    Commented Dec 8, 2014 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
    Commented Dec 8, 2014 at 14:42
  • $\begingroup$ Yes, you can: both options are mathematically valid since reduction modulo $f$ is a homomorphism. $\endgroup$
    – yyyyyyy
    Commented Dec 8, 2014 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
    Commented Jan 5, 2015 at 8:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.