FAILURE MAP
← Case archive

FA-14831 / Numerics / Open access

Polynomial squarefree characteristic p: euclidean divisor transfer · case 01

The exact polynomial squarefree characteristic p result violates the stated contract at euclidean divisor transfer.

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

ROOT CAUSE

The euclidean divisor transfer step uses r,g instead of g,r.

VERIFIED REPAIR

Use g,r at the euclidean divisor transfer step.

Unsuccessful approach: The partial repair g,[] still violates the euclidean divisor transfer 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])%p
      while r and r[-1]==0:r.pop()
     f,g=r,g
    return len(f)==1
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 1], 2], True), ([[0, 1, 1, 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), ([[2, 2], 2], False)], [([[1, 1], 2], True), ([[1, 0, 2, 1], 2], 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)], [([[2, 1], 2], True), ([[1, 2, 0, 1], 2], 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, 1, 1], 2], True), ([[2, 1, 1, 1], 2], 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, 1, 2], 2], True), ([[0, 2, 1], 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 1TrueTruePassed
explicit oracle 2FalseTrueFailed
explicit oracle 3FalseFalsePassed
explicit oracle 4FalseTrueFailed
explicit oracle 5FalseFalsePassed
explicit oracle 6FalseTrueFailed
explicit oracle 7FalseFalsePassed

SHA-256 / 110b2f2cc941d75b4bda6a3b4da6251d88451d1e7a8b70a02a275af6da40622a

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,[]
    return len(f)==1
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 1], 2], True), ([[0, 1, 1, 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), ([[2, 2], 2], False)], [([[1, 1], 2], True), ([[1, 0, 2, 1], 2], 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)], [([[2, 1], 2], True), ([[1, 2, 0, 1], 2], 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, 1, 1], 2], True), ([[2, 1, 1, 1], 2], 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, 1, 2], 2], True), ([[0, 2, 1], 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 1FalseTrueFailed
explicit oracle 2FalseTrueFailed
explicit oracle 3FalseFalsePassed
explicit oracle 4TrueTruePassed
explicit oracle 5FalseFalsePassed
explicit oracle 6TrueTruePassed
explicit oracle 7FalseFalsePassed

SHA-256 / b7e2bedef68f9c535b36d06c0eb60ffaae93d1edbf31796256cc01f8da5ab93a

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 = [[([[0, 1], 2], True), ([[0, 1, 1, 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), ([[2, 2], 2], False)], [([[1, 1], 2], True), ([[1, 0, 2, 1], 2], 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)], [([[2, 1], 2], True), ([[1, 2, 0, 1], 2], 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, 1, 1], 2], True), ([[2, 1, 1, 1], 2], 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, 1, 2], 2], True), ([[0, 2, 1], 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 3FalseFalsePassed
explicit oracle 4TrueTruePassed
explicit oracle 5FalseFalsePassed
explicit oracle 6TrueTruePassed
explicit oracle 7FalseFalsePassed

SHA-256 / 854a7d7b795db0765e1a82026061d95b2fb0551f098a9a6b3086a416dc994623

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

Case digest / b349ca5077e825ff2359559b571677cf001d329afc697bb078c30644bb7023d7