Exercise 2 – Finite Fields 𝔽

Recognition

Work in:

𝔽_p[X] / (P(X)), α = [X]

Typical tasks:

Test if α is a generator
Compute powers
Compute inverses

If called a field, assume P(X) is irreducible.

Core Rule (No Mixing)

Compute in X → final answer in α

Never mix representations during computation.

Step 0: Reduction Rule (GENERAL)

From:

P(X) = X^k + a_k−1·X^k−1 + … + a₀

derive:

X^k ≡ −(a_k−1·X^k−1 + … + a₀) (mod p)

Important: all coefficients are reduced mod p.

Example (only in 𝔽₂):

X⁴ + X + 1 = 0 ⇒ X⁴ ≡ X + 1

Structure Facts

Let deg(P) = k.

|K| = p^k, |K*| = N = p^k − 1 a^N = 1 (a ≠ 0) (a^m)⁻¹ = a^N−m

Generator Test

Factor:

N = Π q_i

Check only:

α^N/q_i

Decision:

α is a generator ⇔ ∀ q_i : α^N/q_i ≠ 1

Inverse Methods

Method 1: Exponent Method (fast)

If element is α^m:

(α^m)⁻¹ = α^N−m

Use repeated squaring + reduction via P(X).

Best when element is already a power of α.

Method 2: Extended Euclidean Algorithm (EEA)

Use when element is a polynomial in α.

Goal:

A(X)⁻¹ mod P(X)

Step 1 (Euclidean algorithm):

P(X) = Q₁·A(X) + R₁, A(X) = Q₂·R₁ + R₂, …

until:

R_k = 1

Step 2 (Bezout identity):

1 = U(X)·A(X) + V(X)·P(X)

Step 3 (mod reduction):

V(X)·P(X) ≡ 0 ⇒ 1 ≡ U(X)·A(X)

Thus:

A(X)⁻¹ = U(X) (mod P(X))

Worked Pattern (EEA Example)

Given:

P(X) = X⁴ + X + 1, A(X) = X² + 1

Forward:

X⁴ + X + 1 = (X² + 1)² + X X² + 1 = X · X + 1

Backward (compressed form):

1 = (X² + 1)(X³ + X + 1) + X(X⁴ + X + 1)

Modulo P(X):

X(X⁴ + X + 1) ≡ 0

So:

(X² + 1)⁻¹ ≡ X³ + X + 1

Back to α:

α⁻⁸ = α³ + α + 1

Exam Template

𝔽₂[X] / (X⁴ + X + 1), N = 15

Generator test:

α³, α⁵

Inverse:

(α⁸)⁻¹ = α⁷

or use EEA if expression is not a pure power.

Shortcuts

Only test exponents N/q
Reduce after every multiplication
EEA avoids discrete log
Exponent method avoids polynomial algebra

Common Mistakes

Mixing X and α
Forgetting coefficient reduction mod p
Using exponent method on non-powers

Exercise 2 Cheat Sheet

Finite Fields 𝔽_p[X]/(P(X)): Generators, Powers & Inverses