Polynome in ℤ₂

Ein Polynom n-ten Grades in ℤ₂ ist ein Polynom der Form $a$_nxⁿ + a_n-1x^n-1 + … + a₂x² + a₁x + a₀ mit Koeffizienten $a$_i ∈ ℤ₂ ($0\; \le \; i\; \le \; n$).

In ℤ₂ = {0,1} gelten die folgenden Rechenregeln: $0\; +\; 0\; =\; 0$, $0\; +\; 1\; =\; 1$, $1\; +\; 0\; =\; 1$, $1\; +\; 1\; =\; 0$ sowie $0\; ·\; 0=0$, $0\; ·\; 1\; =\; 0$, $1\; ·\; 0\; =\; 0$, $1\; ·1\; =\; 1$.

In der verkürzten Darstellung wird ein Polynome in ℤ durch die Folge seiner Koeffizienten repräsentiert, wobei wir vereinbaren, dass der höchstwertige Koeffizient ganz links steht. Beispiel: $1\; ·\; x4+\; 0\; ·\; x3+\; 1\; ·\; x2+\; 1\; ·\; x\; +\; 0$ ↔ $1\; 0\; 1\; 1\; 0$