FA-15641 / Numerics / Open access
Binary field inversion: first polynomial Bezout seed · case 01
The exact binary field inversion result violates the stated contract at first polynomial Bezout seed.
ROOT CAUSE
The first polynomial Bezout seed step uses 0 instead of 1.
VERIFIED REPAIR
Use 1 at the first polynomial Bezout seed step.
Unsuccessful approach: The partial repair a still violates the first polynomial Bezout seed 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=0;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 = [[([1, 7], 1), ([2, 7], 3), ([63, 67], 32), ([3, 7], 2), ([1, 11], 1), ([2, 11], 5), ([3, 11], 6), ([4, 11], 7)], [([2, 7], 3), ([3, 11], 6), ([1, 7], 1), ([63, 67], 32), ([8, 19], 15), ([9, 19], 2), ([10, 19], 12), ([11, 19], 5)], [([3, 7], 2), ([6, 11], 3), ([1, 7], 1), ([63, 67], 32), ([10, 25], 11), ([11, 25], 10), ([12, 25], 2), ([13, 25], 9)], [([1, 11], 1), ([3, 19], 14), ([1, 7], 1), ([63, 67], 32), ([12, 31], 13), ([13, 31], 12), ([14, 31], 11), ([15, 31], 2)], [([2, 11], 5), ([6, 19], 7), ([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 | 0 | 1 | Failed |
| explicit oracle 1 | 0 | 3 | Failed |
| explicit oracle 2 | 0 | 32 | Failed |
| explicit oracle 3 | 0 | 2 | Failed |
| explicit oracle 4 | 0 | 1 | Failed |
| explicit oracle 5 | 0 | 5 | Failed |
| explicit oracle 6 | 0 | 6 | Failed |
| explicit oracle 7 | 0 | 7 | Failed |
SHA-256 / 822b5e1b300c97bccc2eede326db0ff84288705e695bc352e1ddc0b747fbac20
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=a;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 = [[([1, 7], 1), ([2, 7], 3), ([63, 67], 32), ([3, 7], 2), ([1, 11], 1), ([2, 11], 5), ([3, 11], 6), ([4, 11], 7)], [([2, 7], 3), ([3, 11], 6), ([1, 7], 1), ([63, 67], 32), ([8, 19], 15), ([9, 19], 2), ([10, 19], 12), ([11, 19], 5)], [([3, 7], 2), ([6, 11], 3), ([1, 7], 1), ([63, 67], 32), ([10, 25], 11), ([11, 25], 10), ([12, 25], 2), ([13, 25], 9)], [([1, 11], 1), ([3, 19], 14), ([1, 7], 1), ([63, 67], 32), ([12, 31], 13), ([13, 31], 12), ([14, 31], 11), ([15, 31], 2)], [([2, 11], 5), ([6, 19], 7), ([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 | 1 | Passed |
| explicit oracle 1 | 1 | 3 | Failed |
| explicit oracle 2 | 1 | 32 | Failed |
| explicit oracle 3 | 1 | 2 | Failed |
| explicit oracle 4 | 1 | 1 | Passed |
| explicit oracle 5 | 1 | 5 | Failed |
| explicit oracle 6 | 1 | 6 | Failed |
| explicit oracle 7 | 1 | 7 | Failed |
SHA-256 / 0355242c2438809df9ddd9f33d0b92ac58edbfee494466489c3e08d0178aa6b0
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 = [[([1, 7], 1), ([2, 7], 3), ([63, 67], 32), ([3, 7], 2), ([1, 11], 1), ([2, 11], 5), ([3, 11], 6), ([4, 11], 7)], [([2, 7], 3), ([3, 11], 6), ([1, 7], 1), ([63, 67], 32), ([8, 19], 15), ([9, 19], 2), ([10, 19], 12), ([11, 19], 5)], [([3, 7], 2), ([6, 11], 3), ([1, 7], 1), ([63, 67], 32), ([10, 25], 11), ([11, 25], 10), ([12, 25], 2), ([13, 25], 9)], [([1, 11], 1), ([3, 19], 14), ([1, 7], 1), ([63, 67], 32), ([12, 31], 13), ([13, 31], 12), ([14, 31], 11), ([15, 31], 2)], [([2, 11], 5), ([6, 19], 7), ([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 | 1 | Passed |
| explicit oracle 1 | 3 | 3 | Passed |
| explicit oracle 2 | 32 | 32 | Passed |
| explicit oracle 3 | 2 | 2 | Passed |
| explicit oracle 4 | 1 | 1 | Passed |
| explicit oracle 5 | 5 | 5 | Passed |
| explicit oracle 6 | 6 | 6 | Passed |
| explicit oracle 7 | 7 | 7 | Passed |
SHA-256 / 60642d2df71ac511289e3f63e6ecf001cd7d7d4f2be4a8ef3493b1d170ae9c60
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.777482+00:00.
Case digest / 55a116643c53e680d9ba184874380079c0f70dd545efd53ab58b04b5144d241d