FA-15656 / Numerics / Open access
Binary field inversion: polynomial Bezout update · case 01
The exact binary field inversion result violates the stated contract at polynomial Bezout update.
ROOT CAUSE
The polynomial Bezout update step uses g1^(g2>>j) instead of g1^(g2<<j).
VERIFIED REPAIR
Use g1^(g2<<j) at the polynomial Bezout update step.
Unsuccessful approach: The partial repair g1+(g2<<j) still violates the polynomial Bezout update invariant.
Case contract
Input [a,irreducible bitmask], a nonzero with degree below modulus; return multiplicative inverse in binary field. Bounds: modulus degree is between two and six.
Why this case matters
Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
a,p=x;u=a;v=p;g1=1;g2=0
for _ in range(60):
if u==1:break
if u==0:return None
j=u.bit_length()-v.bit_length()
if j<0:
u,v=v,u;g1,g2=g2,g1;j=-j
u=u^(v<<j)
g1=g1^(g2>>j)
for _ in range(60):
if g1.bit_length()<p.bit_length():break
g1=g1^(p<<(g1.bit_length()-p.bit_length()))
return g1
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, 7], 3), ([7, 11], 4), ([1, 7], 1), ([63, 67], 32), ([3, 7], 2), ([1, 11], 1), ([2, 11], 5), ([3, 11], 6)], [([3, 7], 2), ([13, 19], 4), ([1, 7], 1), ([63, 67], 32), ([8, 19], 15), ([9, 19], 2), ([10, 19], 12), ([11, 19], 5)], [([2, 11], 5), ([10, 25], 11), ([1, 7], 1), ([63, 67], 32), ([11, 25], 10), ([12, 25], 2), ([13, 25], 9), ([14, 25], 7)], [([3, 11], 6), ([8, 31], 4), ([1, 7], 1), ([63, 67], 32), ([12, 31], 13), ([13, 31], 12), ([14, 31], 11), ([15, 31], 2)], [([4, 11], 7), ([13, 31], 12), ([1, 7], 1), ([63, 67], 32), ([14, 37], 6), ([15, 37], 13), ([16, 37], 11), ([17, 37], 24)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("explicit oracle %d" % i, 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 |
|---|---|---|---|
| explicit oracle 0 | 1 | 3 | Failed |
| explicit oracle 1 | 0 | 4 | Failed |
| explicit oracle 2 | 1 | 1 | Passed |
| explicit oracle 3 | 0 | 32 | Failed |
| explicit oracle 4 | 0 | 2 | Failed |
| explicit oracle 5 | 1 | 1 | Passed |
| explicit oracle 6 | 1 | 5 | Failed |
| explicit oracle 7 | 0 | 6 | Failed |
SHA-256 / 9b7cd16bc3a917ff09b347ba2a2ca9270919f5465e6244087fc5ae0fee63f1bb
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
a,p=x;u=a;v=p;g1=1;g2=0
for _ in range(60):
if u==1:break
if u==0:return None
j=u.bit_length()-v.bit_length()
if j<0:
u,v=v,u;g1,g2=g2,g1;j=-j
u=u^(v<<j)
g1=g1+(g2<<j)
for _ in range(60):
if g1.bit_length()<p.bit_length():break
g1=g1^(p<<(g1.bit_length()-p.bit_length()))
return g1
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, 7], 3), ([7, 11], 4), ([1, 7], 1), ([63, 67], 32), ([3, 7], 2), ([1, 11], 1), ([2, 11], 5), ([3, 11], 6)], [([3, 7], 2), ([13, 19], 4), ([1, 7], 1), ([63, 67], 32), ([8, 19], 15), ([9, 19], 2), ([10, 19], 12), ([11, 19], 5)], [([2, 11], 5), ([10, 25], 11), ([1, 7], 1), ([63, 67], 32), ([11, 25], 10), ([12, 25], 2), ([13, 25], 9), ([14, 25], 7)], [([3, 11], 6), ([8, 31], 4), ([1, 7], 1), ([63, 67], 32), ([12, 31], 13), ([13, 31], 12), ([14, 31], 11), ([15, 31], 2)], [([4, 11], 7), ([13, 31], 12), ([1, 7], 1), ([63, 67], 32), ([14, 37], 6), ([15, 37], 13), ([16, 37], 11), ([17, 37], 24)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("explicit oracle %d" % i, 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 |
|---|---|---|---|
| explicit oracle 0 | 3 | 3 | Passed |
| explicit oracle 1 | 1 | 4 | Failed |
| explicit oracle 2 | 1 | 1 | Passed |
| explicit oracle 3 | 29 | 32 | Failed |
| explicit oracle 4 | 2 | 2 | Passed |
| explicit oracle 5 | 1 | 1 | Passed |
| explicit oracle 6 | 5 | 5 | Passed |
| explicit oracle 7 | 6 | 6 | Passed |
SHA-256 / d1c3f380a7c0c39cb5094eb65224d630a593b53942542752eb0c735c34665b53
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
a,p=x;u=a;v=p;g1=1;g2=0
for _ in range(60):
if u==1:break
if u==0:return None
j=u.bit_length()-v.bit_length()
if j<0:
u,v=v,u;g1,g2=g2,g1;j=-j
u=u^(v<<j)
g1=g1^(g2<<j)
for _ in range(60):
if g1.bit_length()<p.bit_length():break
g1=g1^(p<<(g1.bit_length()-p.bit_length()))
return g1
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, 7], 3), ([7, 11], 4), ([1, 7], 1), ([63, 67], 32), ([3, 7], 2), ([1, 11], 1), ([2, 11], 5), ([3, 11], 6)], [([3, 7], 2), ([13, 19], 4), ([1, 7], 1), ([63, 67], 32), ([8, 19], 15), ([9, 19], 2), ([10, 19], 12), ([11, 19], 5)], [([2, 11], 5), ([10, 25], 11), ([1, 7], 1), ([63, 67], 32), ([11, 25], 10), ([12, 25], 2), ([13, 25], 9), ([14, 25], 7)], [([3, 11], 6), ([8, 31], 4), ([1, 7], 1), ([63, 67], 32), ([12, 31], 13), ([13, 31], 12), ([14, 31], 11), ([15, 31], 2)], [([4, 11], 7), ([13, 31], 12), ([1, 7], 1), ([63, 67], 32), ([14, 37], 6), ([15, 37], 13), ([16, 37], 11), ([17, 37], 24)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
check("explicit oracle %d" % i, 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 |
|---|---|---|---|
| explicit oracle 0 | 3 | 3 | Passed |
| explicit oracle 1 | 4 | 4 | Passed |
| explicit oracle 2 | 1 | 1 | Passed |
| explicit oracle 3 | 32 | 32 | Passed |
| explicit oracle 4 | 2 | 2 | Passed |
| explicit oracle 5 | 1 | 1 | Passed |
| explicit oracle 6 | 5 | 5 | Passed |
| explicit oracle 7 | 6 | 6 | Passed |
SHA-256 / 03c950878e51b0e9acfb1fe77d44235085533badba99d1b39caca169754a6e75
Verification & scope
A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. 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:39:28.776713+00:00.
Case digest / 0b5873cfde0479f14b56a0196fae4dcaae9a24042a84e70b6e29c66922353a8b