FA-14821 / Numerics / Open access

Polynomial squarefree characteristic p: field leading cancellation · case 01

The exact polynomial squarefree characteristic p result violates the stated contract at field leading cancellation.

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

ROOT CAUSE

The field leading cancellation step uses r[-1]//g[-1] instead of r[-1]*pow(g[-1],-1,p)%p.

VERIFIED REPAIR

Use r[-1]*pow(g[-1],-1,p)%p at the field leading cancellation step.

Unsuccessful approach: The partial repair r[-1]*g[-1]%p still violates the field leading cancellation 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]//g[-1]
      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, 1], 3], True), ([[0, 2], 5], 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, 2, 1], 3], True), ([[0, 1, 1], 5], 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)], [([[1, 0, 1], 3], True), ([[1, 1, 1], 5], 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)], [([[2, 0, 1], 3], True), ([[2, 2, 1], 5], 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)], [([[2, 1, 1], 3], True), ([[0, 1, 2, 2], 5], 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 fixture	Actual	Expected	Outcome
explicit oracle 0	`False`	`True`	Failed
explicit oracle 1	`True`	`True`	Passed
explicit oracle 2	`True`	`True`	Passed
explicit oracle 3	`False`	`True`	Failed
explicit oracle 4	`False`	`False`	Passed
explicit oracle 5	`True`	`True`	Passed
explicit oracle 6	`False`	`False`	Passed
explicit oracle 7	`True`	`True`	Passed

SHA-256 / 61ae6d506a31104d32ae01c88522356ab7e937f9a6139da19122848a34007fd1

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]*g[-1]%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, 1], 3], True), ([[0, 2], 5], 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, 2, 1], 3], True), ([[0, 1, 1], 5], 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)], [([[1, 0, 1], 3], True), ([[1, 1, 1], 5], 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)], [([[2, 0, 1], 3], True), ([[2, 2, 1], 5], 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)], [([[2, 1, 1], 3], True), ([[0, 1, 2, 2], 5], 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 fixture	Actual	Expected	Outcome
explicit oracle 0	`True`	`True`	Passed
explicit oracle 1	`False`	`True`	Failed
explicit oracle 2	`True`	`True`	Passed
explicit oracle 3	`False`	`True`	Failed
explicit oracle 4	`False`	`False`	Passed
explicit oracle 5	`True`	`True`	Passed
explicit oracle 6	`False`	`False`	Passed
explicit oracle 7	`True`	`True`	Passed

SHA-256 / 4b710f0a4d9811b36bf09cef173545cad8de5d537794e5bfaae7e30f3fbd4705

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, 1], 3], True), ([[0, 2], 5], 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, 2, 1], 3], True), ([[0, 1, 1], 5], 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)], [([[1, 0, 1], 3], True), ([[1, 1, 1], 5], 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)], [([[2, 0, 1], 3], True), ([[2, 2, 1], 5], 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)], [([[2, 1, 1], 3], True), ([[0, 1, 2, 2], 5], 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 fixture	Actual	Expected	Outcome
explicit oracle 0	`True`	`True`	Passed
explicit oracle 1	`True`	`True`	Passed
explicit oracle 2	`True`	`True`	Passed
explicit oracle 3	`True`	`True`	Passed
explicit oracle 4	`False`	`False`	Passed
explicit oracle 5	`True`	`True`	Passed
explicit oracle 6	`False`	`False`	Passed
explicit oracle 7	`True`	`True`	Passed

SHA-256 / ea42789aa48eba1429e2c6c8d903145be793b5fb65100c3b2fcec5ca06c9ce67

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

Case digest / 3051c032a3e59f6743d28a925ce344f382f5ce1ed150ca4b1afdaf694dcdc7d9