FA-71956 / Error-correcting codes / Open access

GF(256) multiply reduces with the AES polynomial · case 01

Products that overflow the byte disagree with the Reed-Solomon field.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The reduction XORs 0x1B (x^8+x^4+x^3+x+1) instead of 0x1D.

VERIFIED REPAIR

Reduce with the low byte of 0x11D, i.e. 0x1D.

Unsuccessful approach: XORing the full 0x11D after masking re-introduces bit 8 into the operand.

Case contract

Multiply two elements of GF(2^8) defined by the primitive polynomial x^8+x^4+x^3+x^2+1 (0x11D) using shift-and-add. Operands outside 0..255 return None.

Why this case matters

Reed-Solomon codecs for storage and QR codes are built on GF(2^8) arithmetic with polynomial 0x11D.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(a, b):
    if not (0 <= a < 256 and 0 <= b < 256):
        return None
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        b >>= 1
        carry = a & 0x80
        a = (a << 1) & 0xFF
        if carry:
            a ^= 0x1B
    return p
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [158, 185]', [158, 185], 141], ['regression [66, 7]', [66, 7], 211], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None], ['control [184, 92]', [184, 92], 29]], [['regression [198, 115]', [198, 115], 153], ['regression [136, 144]', [136, 144], 15], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None], ['control [232, 214]', [232, 214], 217]], [['regression [243, 34]', [243, 34], 240], ['regression [9, 184]', [9, 184], 17], ['partial-repair [44, 122]', [44, 122], 249], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None]], [['regression [44, 122]', [44, 122], 249], ['regression [232, 214]', [232, 214], 217], ['partial-repair [231, 130]', [231, 130], 45], ['partial-repair [253, 149]', [253, 149], 58], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9]], [['regression [231, 130]', [231, 130], 45], ['regression [28, 61]', [28, 61], 246], ['partial-repair [117, 177]', [117, 177], 104], ['partial-repair [197, 117]', [197, 117], 168], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression [158, 185]	`100`	`141`	Failed
regression [66, 7]	`213`	`211`	Failed
control [2, 96]	`192`	`192`	Passed
control [0, 5]	`0`	`0`	Passed
control [1, 200]	`200`	`200`	Passed
control [3, 7]	`9`	`9`	Passed
control [256, 1]	`None`	`None`	Passed
control [184, 92]	`219`	`29`	Failed

SHA-256 / fc4015a04d28106043967a4fb0c1eee494adf2150ef20ab6ec034a5d32e22cda

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(a, b):
    if not (0 <= a < 256 and 0 <= b < 256):
        return None
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        b >>= 1
        carry = a & 0x80
        a = (a << 1) & 0xFF
        if carry:
            a ^= 0x11D
    return p
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [158, 185]', [158, 185], 141], ['regression [66, 7]', [66, 7], 211], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None], ['control [184, 92]', [184, 92], 29]], [['regression [198, 115]', [198, 115], 153], ['regression [136, 144]', [136, 144], 15], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None], ['control [232, 214]', [232, 214], 217]], [['regression [243, 34]', [243, 34], 240], ['regression [9, 184]', [9, 184], 17], ['partial-repair [44, 122]', [44, 122], 249], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None]], [['regression [44, 122]', [44, 122], 249], ['regression [232, 214]', [232, 214], 217], ['partial-repair [231, 130]', [231, 130], 45], ['partial-repair [253, 149]', [253, 149], 58], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9]], [['regression [231, 130]', [231, 130], 45], ['regression [28, 61]', [28, 61], 246], ['partial-repair [117, 177]', [117, 177], 104], ['partial-repair [197, 117]', [197, 117], 168], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression [158, 185]	`397`	`141`	Failed
regression [66, 7]	`467`	`211`	Failed
control [2, 96]	`192`	`192`	Passed
control [0, 5]	`0`	`0`	Passed
control [1, 200]	`200`	`200`	Passed
control [3, 7]	`9`	`9`	Passed
control [256, 1]	`None`	`None`	Passed
control [184, 92]	`285`	`29`	Failed

SHA-256 / fc20360281b860de239171b74a47ff00b40bca66dd9193ac5bc1c6cdf378a374

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(a, b):
    if not (0 <= a < 256 and 0 <= b < 256):
        return None
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a
        b >>= 1
        carry = a & 0x80
        a = (a << 1) & 0xFF
        if carry:
            a ^= 0x1D
    return p
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['regression [158, 185]', [158, 185], 141], ['regression [66, 7]', [66, 7], 211], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None], ['control [184, 92]', [184, 92], 29]], [['regression [198, 115]', [198, 115], 153], ['regression [136, 144]', [136, 144], 15], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None], ['control [232, 214]', [232, 214], 217]], [['regression [243, 34]', [243, 34], 240], ['regression [9, 184]', [9, 184], 17], ['partial-repair [44, 122]', [44, 122], 249], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9], ['control [256, 1]', [256, 1], None]], [['regression [44, 122]', [44, 122], 249], ['regression [232, 214]', [232, 214], 217], ['partial-repair [231, 130]', [231, 130], 45], ['partial-repair [253, 149]', [253, 149], 58], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9]], [['regression [231, 130]', [231, 130], 45], ['regression [28, 61]', [28, 61], 246], ['partial-repair [117, 177]', [117, 177], 104], ['partial-repair [197, 117]', [197, 117], 168], ['control [2, 96]', [2, 96], 192], ['control [0, 5]', [0, 5], 0], ['control [1, 200]', [1, 200], 200], ['control [3, 7]', [3, 7], 9]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
regression [158, 185]	`141`	`141`	Passed
regression [66, 7]	`211`	`211`	Passed
control [2, 96]	`192`	`192`	Passed
control [0, 5]	`0`	`0`	Passed
control [1, 200]	`200`	`200`	Passed
control [3, 7]	`9`	`9`	Passed
control [256, 1]	`None`	`None`	Passed
control [184, 92]	`29`	`29`	Passed

SHA-256 / 5f490904cd6374e51f8a1e826cd5747332c531d756592dd1ee282c28f2ca04c2

Verification & scope

A deterministic, bounded teaching model of the named code under the stated contract; not a production codec. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:34.184520+00:00.

Case digest / 9f8fa96095283d50cd1cb125a148c325caaf216c3af26ac48e10d9262c655487