# Exercise 2 Cheat Sheet
## Finite Fields F_p[X]/(P(X)): Generators, Powers & Inverses

---

## Recognition

Work in:

    F_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_0

derive:

    X^k ≡ -(a_{k-1}*X^{k-1} + ... + a_0)  (mod p)

**Important:** all coefficients are reduced mod p.

Example (only in F_2):

    X^4 + X + 1 = 0  ⇒  X^4 ≡ X + 1

---

## Structure Facts

Let deg(P) = k.

    |K| = p^k,    |K*| = N = p^k - 1

    a^N = 1    (a ≠ 0)

    (a^m)^(-1) = 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)^(-1) = α^(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)^(-1) mod P(X)

**Step 1 (Euclidean algorithm):**

    P(X) = Q1*A(X) + R1,    A(X) = Q2*R1 + R2,  ...

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)^(-1) = U(X)  (mod P(X))                        │
    └───────────────────────────────────────────────────────┘

---

## Worked Pattern (EEA Example)

Given:

    P(X) = X^4 + X + 1,    A(X) = X^2 + 1

**Forward:**

    X^4 + X + 1 = (X^2 + 1)^2 + X

    X^2 + 1 = X * X + 1

**Backward (compressed form):**

    1 = (X^2 + 1)(X^3 + X + 1) + X(X^4 + X + 1)

Modulo P(X):

    X(X^4 + X + 1) ≡ 0

So:

    (X^2 + 1)^(-1) ≡ X^3 + X + 1

Back to α:

    ┌───────────────────────────────────────────────┐
    │  α^(-8) = α^3 + α + 1                        │
    └───────────────────────────────────────────────┘

---

## Exam Template

    F_2[X] / (X^4 + X + 1),    N = 15

Generator test:

    α^3,  α^5

Inverse:

    (α^8)^(-1) = α^7

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

---

    ┌───────────────────────────────────────────────────────┐
    │  |K*| = p^k - 1,   (a^m)^(-1) = a^(N-m),             │
    │  a is primitive ⇔ a^(N/q) ≠ 1                        │
    └───────────────────────────────────────────────────────┘