🧩 CLASSIC McELIECE · SIMPLE WALKTHROUGH

col: α₁=1 α₂=2 α₃=3 α₄=4 Row 1: ⎡ 4 3 5 5 ⎤ Row 2: ⎣ 4 6 1 6 ⎦

H = S · Ĥ · P S = Row Mixer — a (2×2) matrix that blends the 2 rows of Ĥ Ĥ = Private matrix from Step 2 — (2 rows × 4 columns) P = Column Shuffler — a (4×4) matrix that reorders the 4 columns of Ĥ Why those sizes? S is (2×2) because Ĥ has 2 rows → S·Ĥ still has 2 rows P is (4×4) because Ĥ has 4 cols → Ĥ·P still has 4 cols Result H is always (2 rows × 4 cols), same shape as Ĥ

Real scheme — S could be any invertible (2×2), e.g.: ⎡ 3 1 ⎤ ← Row 1 of S: [3, 1] ⎣ 2 5 ⎦ ← Row 2 of S: [2, 5] This example — S is the (2×2) identity matrix (multiplying by it changes nothing): ⎡ 1 0 ⎤ ← "1 times row 1 of Ĥ, plus 0 times row 2" = row 1 unchanged ⎣ 0 1 ⎦ ← "0 times row 1 of Ĥ, plus 1 times row 2" = row 2 unchanged

Real scheme — P could shuffle columns, e.g. swap col 1 ↔ col 3: col: 1 2 3 4 ⎡ 0 0 1 0 ⎤ ← new col 1 comes from old col 3 ⎢ 0 1 0 0 ⎥ ← new col 2 comes from old col 2 (unchanged) ⎢ 1 0 0 0 ⎥ ← new col 3 comes from old col 1 ⎣ 0 0 0 1 ⎦ ← new col 4 comes from old col 4 (unchanged) This example — P is the (4×4) identity matrix (columns stay in place): col: 1 2 3 4 ⎡ 1 0 0 0 ⎤ ← col 1 stays as col 1 ⎢ 0 1 0 0 ⎥ ← col 2 stays as col 2 ⎢ 0 0 1 0 ⎥ ← col 3 stays as col 3 ⎣ 0 0 0 1 ⎦ ← col 4 stays as col 4

Ĥ = ⎡ 4 3 5 5 ⎤ S = ⎡ 1 0 ⎤ ⎣ 4 6 1 6 ⎦ ⎣ 0 1 ⎦

S · Ĥ = ⎡ 4 3 5 5 ⎤ ← identical to Ĥ (identity S changed nothing) ⎣ 4 6 1 6 ⎦

P = identity, so each column of P has exactly one "1" and three "0"s. New col 1 of result = P col 1 = [1,0,0,0]ᵀ → take 1×(old col 1) + 0+0+0 = old col 1 New col 2 of result = P col 2 = [0,1,0,0]ᵀ → take old col 2 New col 3 of result = P col 3 = [0,0,1,0]ᵀ → take old col 3 New col 4 of result = P col 4 = [0,0,0,1]ᵀ → take old col 4

H = S · Ĥ · P Because both S and P are identity matrices in this example, every row and column came through unchanged: H = Ĥ = ⎡ 4 3 5 5 ⎤ ⎣ 4 6 1 6 ⎦ In the real scheme S and P are random, so H would look like meaningless noise — that is the whole point of the scrambling.

H has 2 rows and 4 columns. v is a vector with 4 entries written as a column. H · vᵀ = ⎡ H-row1 · v ⎤ = ⎡ H[1,1]×v[1] + H[1,2]×v[2] + H[1,3]×v[3] + H[1,4]×v[4] ⎤ ⎣ H-row2 · v ⎦ ⎣ H[2,1]×v[1] + H[2,2]×v[2] + H[2,3]×v[3] + H[2,4]×v[4] ⎦ Each row of H makes one entry of the result by multiplying element-by-element with v and summing everything up. That is called a dot product.

H = ⎡ 4 3 5 5 ⎤ c = [3, 6, 1, 0] ⎣ 4 6 1 6 ⎦

The sender adds e to c position by position (mod 7). Positions 1 and 3 get a +1, positions 2 and 4 are untouched.

y = [4, 6, 2, 0]

Because y = c + e, and H·cᵀ = 0 (valid codeword always gives zero): H · yᵀ = H · (c + e)ᵀ = H·cᵀ + H·eᵀ = 0 + H·eᵀ = H·eᵀ So H·yᵀ and H·eᵀ give the exact same answer. The syndrome only "sees" the error part — the codeword c vanishes.

sk = ( g(X) , α ) = ( X²+1 , [1,2,3,4] ) ← private key (never published) C₀ = s = [2, 5] ← received ciphertext = H·eᵀ (the syndrome)

s₀ = 2 → constant term, s₁ = 5 → coefficient of X S(X) = s₀ + s₁·X = 2 + 5X Think of this as a "polynomial fingerprint" of where the errors are.

At every step we track two things in parallel: r = the current remainder polynomial t = a cofactor polynomial such that S(X) · t ≡ r (mod g(X)) Starting values: r₋₁ = g(X) = X² + 1 t₋₁ = 0 r₀ = S(X) = 5X + 2 t₀ = 1 Each round: divide r_prev by r_current → get quotient q and new remainder r_new Then update: t_new = t_prev_prev − q × t_current Stop when the remainder has degree < t = 2 (i.e. degree 0, a constant). The final t is σ(X), the Error Locator Polynomial.

Degree of r₂ = 0, which is < t = 2 → stop. σ(X) is built from t₂ scaled to monic degree-2 form: σ(X) = X² + 3X + 3