Math 2.0

Number theory Definition

Berlekamp's algorithm

Builds on Finite fieldMonic polynomialPolynomial greatest common divisorNull spaceChinese remainder theorem for rings

Definition

Let 𝔽q\F_q be the finite field with qq elements and let fβˆˆπ”½q[x]f \in \F_q[x] be a monic square-free polynomial of degree nβ‰₯1n \ge 1. Let VV be the 𝔽q\F_q-vector space of polynomials of degree less than nn. The Berlekamp subalgebra of ff is B={g∈V:gq≑g(modf)}.B = \set{g \in V : g^q \equiv g \pmod{f}}. Berlekamp's algorithm factors ff as follows.

  1. Compute the matrix QQ of the 𝔽q\F_q-linear map Vβ†’VV \to V, h↦hqβ€Šmodβ€Šfh \mapsto h^q \bmod f, and a basis of BB as the null space of Qβˆ’IQ - I.
  2. If dim⁑B=1\dim B = 1, then ff is irreducible.
  3. Otherwise take g∈Bg \in B of positive degree; then f=∏sβˆˆπ”½qgcd⁑(f,gβˆ’s)f = \prod_{s \in \F_q} \gcd(f, g - s), and at least two of these factors have positive degree.
  4. Apply step 3 to the factors, with other elements of BB, until there are dim⁑B\dim B factors.

Remarks

By the Chinese remainder theorem, B≅𝔽qkB \cong \F_q^k, where kk is the number of irreducible factors of ff, so dim⁑B=k\dim B = k. Step 3 holds because gqβˆ’g=∏sβˆˆπ”½q(gβˆ’s)g^q - g = \prod_{s \in \F_q} (g - s) and ff divides gqβˆ’gg^q - g; the factors gβˆ’sg - s are pairwise coprime, and none of them is divisible by ff. Example: f=x2+1f = x^2 + 1 over 𝔽5\F_5; since x5≑x(modf)x^5 \equiv x \pmod{f}, B=VB = V has dimension 22, and g=xg = x gives gcd⁑(f,xβˆ’2)=xβˆ’2\gcd(f, x - 2) = x - 2 and gcd⁑(f,xβˆ’3)=xβˆ’3\gcd(f, x - 3) = x - 3. Non-example: f=x2+1f = x^2 + 1 over 𝔽3\F_3; since x3β‰‘βˆ’x(modf)x^3 \equiv -x \pmod{f}, (a+bx)3≑aβˆ’bx(a + bx)^3 \equiv a - bx, so BB is the constants, dim⁑B=1\dim B = 1, and ff is irreducible. The algorithm needs ff square-free; a repeated factor is first removed with gcd⁑(f,fβ€²)\gcd(f, f'). The running time is polynomial in nn and qq, so it suits small fields; for large qq randomised variants are used.

Reading path

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

Show the path as a graph
Group, concept, no evidence levelGroupconceptMatrix, definition, no evidence levelMatrixdefinitionVector space, definition, no evidence levelVector spacedefinitionRing, definition, no evidence levelRingdefinitionLinear map, definition, no evidence levelLinear mapdefinitionCommutative ring, definition, no evidence levelCommutative ringdefinitionIdeal, definition, no evidence levelIdealdefinitionPolynomial ring, definition, no evidence levelPolynomial ringdefinitionProduct of rings, definition, no evidence levelProduct of ringsdefinitionRing homomorphism, definition, no evidence levelRing homomorphismdefinitionUnit of a ring, definition, no evidence levelUnit of a ringdefinitionZero divisor, definition, no evidence levelZero divisordefinitionKernel of a linear map, definition, no evidence levelKernel of a linear mapdefinitionDivisibility in a commutative ring, definition, no evidence levelDivisibility in a com…definitionSum of ideals, concept, no evidence levelSum of idealsconceptTwo-sided ideal, definition, no evidence levelTwo-sided idealdefinitionDegree of a polynomial, definition, no evidence levelDegree of a polynomialdefinitionField, definition, no evidence levelFielddefinitionIntegral domain, definition, no evidence levelIntegral domaindefinitionNull space, definition, no evidence levelNull spacedefinitionRing isomorphism, definition, no evidence levelRing isomorphismdefinitionCoprime ideals, definition, no evidence levelCoprime idealsdefinitionQuotient ring, definition, no evidence levelQuotient ringdefinitionAssociate elements, definition, no evidence levelAssociate elementsdefinitionLeading coefficient, definition, no evidence levelLeading coefficientdefinitionFinite field, definition, no evidence levelFinite fielddefinitionGreatest common divisor in an integral domain, definition, no evidence levelGreatest common divis…definitionChinese remainder theorem for rings, statement, no evidence levelChinese remainder the…statementMonic polynomial, definition, no evidence levelMonic polynomialdefinitionPolynomial greatest common divisor, definition, no evidence levelPolynomial greatest c…definitionBerlekamp's algorithm, definition, no evidence levelBerlekamp's algorithmdefinition
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. Group concept
  2. Matrix definition
  3. Vector space definition
  4. Ring definition
  5. Linear map definition
  6. Commutative ring definition
  7. Ideal definition
  8. Polynomial ring definition
  9. Product of rings definition
  10. Ring homomorphism definition
  11. Unit of a ring definition
  12. Zero divisor definition
  13. Kernel of a linear map definition
  14. Divisibility in a commutative ring definition
  15. Sum of ideals concept
  16. Two-sided ideal definition
  17. Degree of a polynomial definition
  18. Field definition
  19. Integral domain definition
  20. Null space definition
  21. Ring isomorphism definition
  22. Coprime ideals definition
  23. Quotient ring definition
  24. Associate elements definition
  25. Leading coefficient definition
  26. Finite field definition
  27. Greatest common divisor in an integral domain definition
  28. Chinese remainder theorem for rings statement
  29. Monic polynomial definition
  30. Polynomial greatest common divisor definition
  31. Berlekamp's algorithm definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Berlekamp%27s_algorithm
About this page
TagHJW1KSQZWA
URIm2://HJW1KSQZWA
Kinddefinition
WritingW0 stub
MSC11T06, 11Y16, 68W30
DefinesBerlekamp's algorithm
UsesFinite field, Monic polynomial, Polynomial greatest common divisor, Null space, Chinese remainder theorem for rings
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.