Calculations on GF(16) find 0111/1111. It's my first time doing finite field arithmetics. As an exercise, I want to find 0111/1111 in GF(16) generated by Pi(alpha)=1+alpha+alpha^4 that is an irreducible polynomial.

c0nman56 2022-10-26 Answered
Calculations on GF(16) find 0111/1111
It's my first time doing finite field arithmetics. As an exercise, I want to find 0111 / 1111 G F ( 16 ) generated by Π ( α ) = 1 + α + α 4 that is an irreducible polynomial.
In polynomial form we have:
0111 α + α 2 + α 3
1111 1 + α + α 2 + α 3
If I perform the polynomial division, I obtain -1 (that is the same result obtained writing 0111 1 ( mod 1111 ).
How can I compute this result -1 in the right element of the field? Or perhaps this some kind of sign that the result G F ( 16 )?
You can still ask an expert for help

Want to know more about Polynomial arithmetic?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

canhaulatlt
Answered 2022-10-27 Author has 17 answers
Step 1
As it happens, the discrete logarithm table for GF(16) that I prepared for referrals like this, uses the same minimal polynomial of the primitive element. The only difference is that in the linked thread I denote by γ the element that you refer to as α.
Step 2
Anyway, consulting that table, we see that
1111 = 1 + α + α 2 + α 3 = α 12 ,
and
0111 = α + α 2 + α 3 = α 11 .
Therefore
0111 1111 = α 11 α 12 = α 11 α 12 α 3 α 3 = α 14 α 15 = α 14 1 = α 14 = α 3 + 1 = 1001.
Did you like this example?
Subscribe for all access
Kendrick Finley
Answered 2022-10-28 Author has 1 answers
Step 1
GF(16) has characteristic 2. That is, each coefficient of α is either 0 or 1. And 1 = 1.
However, the polynomial division does not just result in -1 or 1. Instead we have:
α 3 + α 2 + α α 3 + α 2 + α + 1 = 1 + 1 α 3 + α 2 + α + 1
As an alternative to the answers in the comments, we can write each element (except 0) as a power of α. After all, GF(16) has a cyclic multiplicative group and α 15 = 1.
Step 2
Over the polynomial X 4 + X + 1 we have 0111 = α 11 and 1111 = α 12 . Therefore:
0111/1111=α11/α12=α11+15−12=α14=1001
This is consistent with your result:
1 + 1 α 3 + α 2 + α + 1 = 1 + 1 α 12 = 1 + α 15 α 12 = 1 + α 3
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more