Math 2.0

Field theory and polynomials Definition

Finite field arithmetic

Builds on Finite fieldIrreducible polynomialPolynomial ringQuotient ringDegree of a polynomialPolynomial long divisionEuclidean algorithm

Definition

Let pp be a prime, let n≥1n \ge 1, and let f∈𝔽p[x]f \in \F_p[x] be a monic irreducible polynomial of degree nn. The quotient ring 𝔽p[x]/(f)\F_p[x]/(f) of the polynomial ring is a finite field with pnp^n elements. Finite field arithmetic in this representation computes with the polynomials a(x)a(x) of degree less than nn over 𝔽p\F_p, one for each element, as follows.

  1. The sum a+ba + b is the coefficientwise sum modulo pp.
  2. The product a⋅ba \cdot b is the remainder of the polynomial product a(x)b(x)a(x) b(x) under division by ff.
  3. The inverse of a≠0a \ne 0 is the polynomial uu of degree less than nn with ua+vf=1u a + v f = 1 for some v∈𝔽p[x]v \in \F_p[x], found by the extended Euclidean algorithm.

Remarks

Take p=2p = 2 and f=x3+x+1f = x^3 + x + 1, which has no root in 𝔽2\F_2 and so is irreducible. Then (x2+1)(x+1)=x3+x2+x+1(x^2 + 1)(x + 1) = x^3 + x^2 + x + 1, and its remainder modulo ff is x2x^2. The inverse of xx is x2+1x^2 + 1, since x(x2+1)=x3+x=f+1x(x^2 + 1) = x^3 + x = f + 1. The polynomial x2+1x^2 + 1 over 𝔽2\F_2 cannot serve as ff, since x2+1=(x+1)2x^2 + 1 = (x + 1)^2, and then x+1x + 1 has no inverse. Over 𝔽2\F_2, an element is stored as the bit string of its coefficients, and addition is the bitwise exclusive or. The inverse can also be computed as apn−2a^{p^n - 2}, since apn−1=1a^{p^n - 1} = 1 for a≠0a \ne 0.

Reading path

To understand this page from the ground up, read these 18 pages in order. The foundations come first.

Show the path as a graph
Euclidean algorithm, concept, no evidence levelEuclidean algorithmconceptGroup, concept, no evidence levelGroupconceptPolynomial long division, concept, no evidence levelPolynomial long divis…conceptRing, definition, no evidence levelRingdefinitionCommutative ring, definition, no evidence levelCommutative ringdefinitionPolynomial ring, definition, no evidence levelPolynomial ringdefinitionUnit of a ring, definition, no evidence levelUnit of a ringdefinitionZero divisor, definition, no evidence levelZero divisordefinitionIdeal, definition, no evidence levelIdealdefinitionDegree of a polynomial, definition, no evidence levelDegree of a polynomialdefinitionField, definition, no evidence levelFielddefinitionIntegral domain, definition, no evidence levelIntegral domaindefinitionTwo-sided ideal, definition, no evidence levelTwo-sided idealdefinitionFinite field, definition, no evidence levelFinite fielddefinitionQuotient ring, definition, no evidence levelQuotient ringdefinitionIrreducible element, definition, no evidence levelIrreducible elementdefinitionIrreducible polynomial, definition, no evidence levelIrreducible polynomialdefinitionFinite field arithmetic, definition, no evidence levelFinite field arithmet…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Euclidean algorithm concept
  2. Group concept
  3. Polynomial long division concept
  4. Ring definition
  5. Commutative ring definition
  6. Polynomial ring definition
  7. Unit of a ring definition
  8. Zero divisor definition
  9. Ideal definition
  10. Degree of a polynomial definition
  11. Field definition
  12. Integral domain definition
  13. Two-sided ideal definition
  14. Finite field definition
  15. Quotient ring definition
  16. Irreducible element definition
  17. Irreducible polynomial definition
  18. Finite field arithmetic definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Finite_field_arithmetic
About this page
Tag92JCZQZSST
URIm2://92JCZQZSST
Kinddefinition
WritingW0 stub
MSC12E20, 11T71, 12-08
DefinesFinite field arithmetic
UsesFinite field, Irreducible polynomial, Polynomial ring, Quotient ring, Degree of a polynomial, Polynomial long division, Euclidean algorithm
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.