FAILURE MAP
← Case archive

FA-14826 / Numerics / Open access

Polynomial squarefree characteristic p: field subtraction reduction · case 01

The exact polynomial squarefree characteristic p result violates the stated contract at field subtraction reduction.

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

ROOT CAUSE

The field subtraction reduction step uses r[j+k]-c*g[j] instead of (r[j+k]-c*g[j])%p.

VERIFIED REPAIR

Use (r[j+k]-c*g[j])%p at the field subtraction reduction step.

Unsuccessful approach: The partial repair (r[j+k]+c*g[j])%p still violates the field subtraction reduction invariant.

Case contract

Input [coefficients,p] prime p; return whether nonconstant polynomial over Fp has gcd(f,fprime)=1; constants false. Bounds: degree at most three and prime p<=7.

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
    f=[v%p for v in a]
    while f and f[-1]==0:f.pop()
    if len(f)<2:return False
    g=[(i*f[i])%p for i in range(1,len(f))]
    while g and g[-1]==0:g.pop()
    for _ in range(20):
     if not g:break
     r=f[:]
     for _ in range(20):
      if len(r)<len(g):break
      if g[-1]%p==0:return None
      c=r[-1]*pow(g[-1],-1,p)%p
      k=len(r)-len(g)
      for j in range(len(g)):r[j+k]=r[j+k]-c*g[j]
      while r and r[-1]==0:r.pop()
     f,g=g,r
    return len(f)==1
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 2], 3], True), ([[0, 1], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 2], 2], False), ([[1, 1], 2], True), ([[1, 2], 2], False), ([[2, 1], 2], True)], [([[0, 1, 1], 3], True), ([[1, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 2, 2], 2], False), ([[2, 0, 1], 2], False), ([[2, 0, 2], 2], False), ([[2, 1, 1], 2], True)], [([[0, 1, 2], 3], True), ([[0, 1, 1], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 1, 2, 1], 2], False), ([[0, 1, 2, 2], 2], True), ([[0, 2, 0, 1], 2], False), ([[0, 2, 0, 2], 2], False)], [([[0, 2, 1], 3], True), ([[0, 2, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 1, 1, 2], 2], True), ([[1, 1, 2, 1], 2], True), ([[1, 1, 2, 2], 2], True), ([[1, 2, 0, 1], 2], True)], [([[0, 2, 2], 3], True), ([[1, 1, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[2, 1, 1, 1], 2], True), ([[2, 1, 1, 2], 2], True), ([[2, 1, 2, 1], 2], False), ([[2, 1, 2, 2], 2], True)]]
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 fixtureActualExpectedOutcome
explicit oracle 0NoneTrueFailed
explicit oracle 1TrueTruePassed
explicit oracle 2TrueTruePassed
explicit oracle 3FalseTrueFailed
explicit oracle 4FalseFalsePassed
explicit oracle 5TrueTruePassed
explicit oracle 6FalseFalsePassed
explicit oracle 7TrueTruePassed

SHA-256 / 7102ceeccb1792e7f7423d3d2d613dc2048d40d75db070e272d407355f5021eb

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
    f=[v%p for v in a]
    while f and f[-1]==0:f.pop()
    if len(f)<2:return False
    g=[(i*f[i])%p for i in range(1,len(f))]
    while g and g[-1]==0:g.pop()
    for _ in range(20):
     if not g:break
     r=f[:]
     for _ in range(20):
      if len(r)<len(g):break
      if g[-1]%p==0:return None
      c=r[-1]*pow(g[-1],-1,p)%p
      k=len(r)-len(g)
      for j in range(len(g)):r[j+k]=(r[j+k]+c*g[j])%p
      while r and r[-1]==0:r.pop()
     f,g=g,r
    return len(f)==1
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 2], 3], True), ([[0, 1], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 2], 2], False), ([[1, 1], 2], True), ([[1, 2], 2], False), ([[2, 1], 2], True)], [([[0, 1, 1], 3], True), ([[1, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 2, 2], 2], False), ([[2, 0, 1], 2], False), ([[2, 0, 2], 2], False), ([[2, 1, 1], 2], True)], [([[0, 1, 2], 3], True), ([[0, 1, 1], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 1, 2, 1], 2], False), ([[0, 1, 2, 2], 2], True), ([[0, 2, 0, 1], 2], False), ([[0, 2, 0, 2], 2], False)], [([[0, 2, 1], 3], True), ([[0, 2, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 1, 1, 2], 2], True), ([[1, 1, 2, 1], 2], True), ([[1, 1, 2, 2], 2], True), ([[1, 2, 0, 1], 2], True)], [([[0, 2, 2], 3], True), ([[1, 1, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[2, 1, 1, 1], 2], True), ([[2, 1, 1, 2], 2], True), ([[2, 1, 2, 1], 2], False), ([[2, 1, 2, 2], 2], True)]]
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 fixtureActualExpectedOutcome
explicit oracle 0FalseTrueFailed
explicit oracle 1FalseTrueFailed
explicit oracle 2TrueTruePassed
explicit oracle 3FalseTrueFailed
explicit oracle 4FalseFalsePassed
explicit oracle 5TrueTruePassed
explicit oracle 6FalseFalsePassed
explicit oracle 7TrueTruePassed

SHA-256 / 4985e8e6ca03efa37b2e98ee192c0cf91477cc2ad19f002ae3380debb1f2b973

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
    f=[v%p for v in a]
    while f and f[-1]==0:f.pop()
    if len(f)<2:return False
    g=[(i*f[i])%p for i in range(1,len(f))]
    while g and g[-1]==0:g.pop()
    for _ in range(20):
     if not g:break
     r=f[:]
     for _ in range(20):
      if len(r)<len(g):break
      if g[-1]%p==0:return None
      c=r[-1]*pow(g[-1],-1,p)%p
      k=len(r)-len(g)
      for j in range(len(g)):r[j+k]=(r[j+k]-c*g[j])%p
      while r and r[-1]==0:r.pop()
     f,g=g,r
    return len(f)==1
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 2], 3], True), ([[0, 1], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 2], 2], False), ([[1, 1], 2], True), ([[1, 2], 2], False), ([[2, 1], 2], True)], [([[0, 1, 1], 3], True), ([[1, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 2, 2], 2], False), ([[2, 0, 1], 2], False), ([[2, 0, 2], 2], False), ([[2, 1, 1], 2], True)], [([[0, 1, 2], 3], True), ([[0, 1, 1], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 1, 2, 1], 2], False), ([[0, 1, 2, 2], 2], True), ([[0, 2, 0, 1], 2], False), ([[0, 2, 0, 2], 2], False)], [([[0, 2, 1], 3], True), ([[0, 2, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 1, 1, 2], 2], True), ([[1, 1, 2, 1], 2], True), ([[1, 1, 2, 2], 2], True), ([[1, 2, 0, 1], 2], True)], [([[0, 2, 2], 3], True), ([[1, 1, 2], 3], True), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[2, 1, 1, 1], 2], True), ([[2, 1, 1, 2], 2], True), ([[2, 1, 2, 1], 2], False), ([[2, 1, 2, 2], 2], True)]]
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 fixtureActualExpectedOutcome
explicit oracle 0TrueTruePassed
explicit oracle 1TrueTruePassed
explicit oracle 2TrueTruePassed
explicit oracle 3TrueTruePassed
explicit oracle 4FalseFalsePassed
explicit oracle 5TrueTruePassed
explicit oracle 6FalseFalsePassed
explicit oracle 7TrueTruePassed

SHA-256 / 17cefc03955c244b95a0774671119eca6bc4ba60ee31f84317ec9795adb3c190

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:20.649584+00:00.

Case digest / 5e4c74ee08b53c867d36a2064e76d993c6d80caffc4479b16fdd4825c3ae6a53