How to calculate multiplicative inverses in G F ( 2 3 ) without the Euclidean algorithmThe problem I have concerns finite field arithmetic in G F ( p k )I know how to find multiplicative inverses using the extended Euclidean algorithm, but for my exams I need to calculate multiplicative inverses in G F ( 2 3 ) without it.What's the best way to do this? Is there even a convenient way?The irreducible polynomial I have is x 3 + x + 1.

Question

How to calculate multiplicative inverses in   G  F  (      2    3    ) without the Euclidean algorithmThe problem I have concerns finite field arithmetic in   G  F  (      p    k    )I know how to find multiplicative inverses using the extended Euclidean algorithm, but for my exams I need to calculate multiplicative inverses in   G  F  (      2    3    ) without it.What&#039;s the best way to do this? Is there even a convenient way?The irreducible polynomial I have is       x    3    +  x  +  1.

Aliya Moore · Accepted Answer

Step 1            F        2   is a pretty small base field, so to find the inverse of an element in             F        2        /    (      x    3    +  x  +  1  )  =            F        8   is always really simple. For instance, let us find the inverse of       x    2    +  x. For any   a  ,  b  ,  c  ∈            F        2    (      x    2    +  x  )  (  a      x    2    +  b  x  +  c  )  =  (  c  +  b  −  a  )      x    2    +  (  c  −  b  )  x  +  (  a  +  b  )holds in             F        2        /    (      x    3    +  x  +  1  ), so the inverse of       x    2    +  x can be found by solving   c  +  b  −  a  =  0  ,  c  −  b  =  0  ,  a  +  b  =  1 in             F        2  , leading to   a  =  0 and   b  =  c  =  1.Step 2Double-check:  (  x  +  1  )  (      x    2    +  x  )  =      x    3    +      x    2    +      x    2    +  x  =      x    3    +  x  =  2  x  +  1  =  1.

Jairo Hodges · Accepted Answer

Step 1As an alternative, build the table of the so called discrete logarithm. Let a be a root of   f  =      x          3        +  x  +  1. Then                                    a                      0                          =        1                                            a                      1                          =        a                                            a                      2                          =                  a                      2                                                              a                      3                          =        a        +        1                                            a                      4                          =                  a                      2                          +        a                                            a                      5                          =                  a                      2                          +        a        +        1                                            a                      6                          =                  a                      2                          +        1                                            a                      7                          =        1            So to compute the inverse of       a          2        +  a, say, you note that       a          2        +  a  =      a          4      . Since       a          7        =  1, the inverse of       a          4       is       a          3        =  a  +  1.Step 2Note that in building the table you are doing Euclidean divisions in a simplified form. For instance      a          5        =      a          4        a  =  (      a          2        +  a  )  a  =      a          3        +      a          2        =  a  +  1  +      a          2      since a is a root of       x          3        +  x  +  1, and thus       a          3        =  a  +  1.

How to calculate multiplicative inverses in GF(2^3) without the Euclidean algorithm

Answered question

Answer & Explanation

New Questions in Algebra II