Polynomial Arithmetic

Polynomial Arithmetic

1. Polynomials over a Field (Why $GF(2)[x]$ Rules Crypto)

A polynomial $a(x) = a_nx^n + \cdots + a_1x + a_0$ with coefficients in a field $F$ behaves like integers: add/subtract termwise, multiply by convolution, divide with remainder. Degree rules: $\deg(f+g) \le \max$, $\deg(fg) = \deg f + \deg g$, division gives $f = qg + r$ with $\deg r < \deg g$. Crypto's home ring: $GF(2)[x]$ — coefficients bits, addition = XOR, subtraction = addition.

2. Worked $GF(2)[x]$ Examples (AES-Style Bytes)

Represent bytes as polynomials: 0x57 $= 01010111 \to x^6+x^4+x^2+x+1$; 0x83 $= 10000011 \to x^7+x+1$.

• Addition: $(x^6+x^4+x^2+x+1) + (x^7+x+1) = x^7+x^6+x^4+x^2$ ($x$ and $1$ cancel: $1 \oplus 1 = 0$) → 0xD4. XOR of bytes: 0x57 ⊕ 0x83 = 0xD4 ✓ — polynomial addition IS byte XOR.
• Multiplication: $(x^2+x+1)(x+1) = x^3+x^2+x + x^2+x+1 = x^3 + (x^2 \oplus x^2) + (x \oplus x) + 1 = x^3+1$ (like terms vanish in pairs). Integer check fails — no carries in $GF(2)$!
• Division: $(x^3+1) \div (x+1)$: $x^3/(x) = x^2$ → multiply-subtract (XOR): remainder $x^2+1$; next $+x$: remainder $x+1$; next $+1$: remainder $0$. Quotient $x^2+x+1$ ✓ (matches multiplication above inverted).

3. GCD, Irreducibles, and Modular Polynomials

• GCD same Euclid with degrees: $\gcd(x^3+1, x+1) = x+1$ (from division above, zero remainder at divisor $x+1$).
• Irreducible = prime-like (no nontrivial factors): $x^3+x+1$ over $GF(2)$ is irreducible (no root $0$ or $1$: $f(0) = 1$, $f(1) = 1+1+1 = 1
  e 0$— degree-3 with no linear factor ⟹ irreducible).$x^2+1 = (x+1)^2$in$GF(2)$ — REDUCIBLE (freshman's dream!), unlike over reals.
• Modular reduction: $x^8 \bmod m(x)$ with AES $m(x) = x^8+x^4+x^3+x+1$: $x^8 \equiv x^4+x^3+x+1$ (move $x^8$ across: $m(x) = 0$). So multiplying bytes that overflow degree 7 reduces via this rule — MixColumns/xtime mechanized.

xtime (× $x$) worked: 0x87 ($x^7+x^2+x+1$) times $x$ = $x^8+x^3+x^2+x$ → reduce $x^8$ → $(x^4+x^3+x+1)+x^3+x^2+x = x^4+x^2+1$ (0x15)... check: $x^3 \oplus x^3 = 0$, $x \oplus x = 0$ → $x^4+x^2+1$ ✓. Rule: left-shift; if bit-7 was set, XOR 0x1B ($m(x)$ without $x^8$).

4. Bridge to $GF(2^n)$ (Next Topic)

Polynomials mod an irreducible degree-$n$ $m(x)$ form field $GF(2^n)$ — exactly how $\mathbb{Z}_p$ came from integers mod prime $p$. AES: bytes mod $m(x)$ degree 8 → $GF(2^8)$; inverse via Extended Euclid on polynomials (same table method, degrees instead of sizes).

Exam Points

• Byte↔polynomial conversion (0x57, 0x83) + XOR-addition to 0xD4 — 2-mark opener.
• Multiplication with pair-cancellation ($(x^2+x+1)(x+1) = x^3+1$) + division trace — 5-mark core.
• Irreducibility test via roots ($x^3+x+1$ irreducible; $x^2+1 = (x+1)^2$ trap!).
• xtime reduction with 0x1B conditional XOR.