FA-15491 / Numerics / Open access

Hensel simple root lift: lifting exponent count · case 01

The exact hensel simple root lift result violates the stated contract at lifting exponent count.

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

ROOT CAUSE

The lifting exponent count step uses range(k) instead of range(1,k).

VERIFIED REPAIR

Use range(1,k) at the lifting exponent count step.

Unsuccessful approach: The partial repair range(1,k-1) still violates the lifting exponent count invariant.

Case contract

Input [coefficients,p,r,k], p prime, r root mod p with nonzero derivative, k>=1; return unique root mod p^k congruent r mod p.

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):
    coeff,p,r,k=x
    mod=p;r%=p
    for _ in range(k):
     value=sum(c*r**i for i,c in enumerate(coeff))
     derivative=sum(i*coeff[i]*r**(i-1) for i in range(1,len(coeff)))
     if derivative%p==0:return None
     correction=(-(value//mod)*pow(derivative,-1,p))%p
     r=r+mod*correction
     mod=mod*p
     r%=mod
    return [r,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 1, 1], 7, 2, 1], [2, 7]), ([[1, 1, 1], 7, 2, 2], [30, 49]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 4, 1], [4, 7]), ([[1, 1, 1], 7, 4, 2], [18, 49])], [([[1, 1, 1], 7, 2, 2], [30, 49]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 13, 9, 3], [1036, 2197]), ([[1, 1, 1], 13, 9, 4], [7627, 28561]), ([[1, 1, 1], 13, 9, 5], [150432, 371293]), ([[-2, 0, 1], 7, 3, 1], [3, 7])], [([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 4, 4], [1047, 2401]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-1, 1, 1], 11, 3, 5], [77234, 161051]), ([[-1, 1, 1], 11, 7, 1], [7, 11]), ([[-1, 1, 1], 11, 7, 2], [84, 121]), ([[-1, 1, 1], 11, 7, 3], [1294, 1331])], [([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 13, 3, 3], [1160, 2197]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 7, 1, 2], [1, 49]), ([[-3, 1, 2], 7, 1, 3], [1, 343]), ([[-3, 1, 2], 7, 1, 4], [1, 2401]), ([[-3, 1, 2], 7, 1, 5], [1, 16807])], [([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 13, 9, 2], [22, 169]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 11, 4, 4], [7319, 14641]), ([[-3, 1, 2], 11, 4, 5], [80524, 161051]), ([[-3, 1, 2], 13, 1, 1], [1, 13]), ([[-3, 1, 2], 13, 1, 2], [1, 169])]]
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	`[30, 49]`	`[2, 7]`	Failed
explicit oracle 1	`[324, 343]`	`[30, 49]`	Failed
explicit oracle 2	`[4826808, 4826809]`	`[371292, 371293]`	Failed
explicit oracle 3	`[1353, 2401]`	`[324, 343]`	Failed
explicit oracle 4	`[1353, 16807]`	`[1353, 2401]`	Failed
explicit oracle 5	`[34967, 117649]`	`[1353, 16807]`	Failed
explicit oracle 6	`[18, 49]`	`[4, 7]`	Failed
explicit oracle 7	`[18, 343]`	`[18, 49]`	Failed

SHA-256 / ca936c7aa754a6ed31902e49cdb040286a7b8a75b86d8628f4af132d052e746a

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):
    coeff,p,r,k=x
    mod=p;r%=p
    for _ in range(1,k-1):
     value=sum(c*r**i for i,c in enumerate(coeff))
     derivative=sum(i*coeff[i]*r**(i-1) for i in range(1,len(coeff)))
     if derivative%p==0:return None
     correction=(-(value//mod)*pow(derivative,-1,p))%p
     r=r+mod*correction
     mod=mod*p
     r%=mod
    return [r,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 1, 1], 7, 2, 1], [2, 7]), ([[1, 1, 1], 7, 2, 2], [30, 49]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 4, 1], [4, 7]), ([[1, 1, 1], 7, 4, 2], [18, 49])], [([[1, 1, 1], 7, 2, 2], [30, 49]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 13, 9, 3], [1036, 2197]), ([[1, 1, 1], 13, 9, 4], [7627, 28561]), ([[1, 1, 1], 13, 9, 5], [150432, 371293]), ([[-2, 0, 1], 7, 3, 1], [3, 7])], [([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 4, 4], [1047, 2401]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-1, 1, 1], 11, 3, 5], [77234, 161051]), ([[-1, 1, 1], 11, 7, 1], [7, 11]), ([[-1, 1, 1], 11, 7, 2], [84, 121]), ([[-1, 1, 1], 11, 7, 3], [1294, 1331])], [([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 13, 3, 3], [1160, 2197]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 7, 1, 2], [1, 49]), ([[-3, 1, 2], 7, 1, 3], [1, 343]), ([[-3, 1, 2], 7, 1, 4], [1, 2401]), ([[-3, 1, 2], 7, 1, 5], [1, 16807])], [([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 13, 9, 2], [22, 169]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 11, 4, 4], [7319, 14641]), ([[-3, 1, 2], 11, 4, 5], [80524, 161051]), ([[-3, 1, 2], 13, 1, 1], [1, 13]), ([[-3, 1, 2], 13, 1, 2], [1, 169])]]
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	`[2, 7]`	`[2, 7]`	Passed
explicit oracle 1	`[2, 7]`	`[30, 49]`	Failed
explicit oracle 2	`[28560, 28561]`	`[371292, 371293]`	Failed
explicit oracle 3	`[30, 49]`	`[324, 343]`	Failed
explicit oracle 4	`[324, 343]`	`[1353, 2401]`	Failed
explicit oracle 5	`[1353, 2401]`	`[1353, 16807]`	Failed
explicit oracle 6	`[4, 7]`	`[4, 7]`	Passed
explicit oracle 7	`[4, 7]`	`[18, 49]`	Failed

SHA-256 / 75f9f6c357fe58d266f92ba8237f26453f36b59731008f55dce3e91a33e71e2a

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):
    coeff,p,r,k=x
    mod=p;r%=p
    for _ in range(1,k):
     value=sum(c*r**i for i,c in enumerate(coeff))
     derivative=sum(i*coeff[i]*r**(i-1) for i in range(1,len(coeff)))
     if derivative%p==0:return None
     correction=(-(value//mod)*pow(derivative,-1,p))%p
     r=r+mod*correction
     mod=mod*p
     r%=mod
    return [r,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 1, 1], 7, 2, 1], [2, 7]), ([[1, 1, 1], 7, 2, 2], [30, 49]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 4, 1], [4, 7]), ([[1, 1, 1], 7, 4, 2], [18, 49])], [([[1, 1, 1], 7, 2, 2], [30, 49]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 13, 9, 3], [1036, 2197]), ([[1, 1, 1], 13, 9, 4], [7627, 28561]), ([[1, 1, 1], 13, 9, 5], [150432, 371293]), ([[-2, 0, 1], 7, 3, 1], [3, 7])], [([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 4, 4], [1047, 2401]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-1, 1, 1], 11, 3, 5], [77234, 161051]), ([[-1, 1, 1], 11, 7, 1], [7, 11]), ([[-1, 1, 1], 11, 7, 2], [84, 121]), ([[-1, 1, 1], 11, 7, 3], [1294, 1331])], [([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 13, 3, 3], [1160, 2197]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 7, 1, 2], [1, 49]), ([[-3, 1, 2], 7, 1, 3], [1, 343]), ([[-3, 1, 2], 7, 1, 4], [1, 2401]), ([[-3, 1, 2], 7, 1, 5], [1, 16807])], [([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 13, 9, 2], [22, 169]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 11, 4, 4], [7319, 14641]), ([[-3, 1, 2], 11, 4, 5], [80524, 161051]), ([[-3, 1, 2], 13, 1, 1], [1, 13]), ([[-3, 1, 2], 13, 1, 2], [1, 169])]]
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	`[2, 7]`	`[2, 7]`	Passed
explicit oracle 1	`[30, 49]`	`[30, 49]`	Passed
explicit oracle 2	`[371292, 371293]`	`[371292, 371293]`	Passed
explicit oracle 3	`[324, 343]`	`[324, 343]`	Passed
explicit oracle 4	`[1353, 2401]`	`[1353, 2401]`	Passed
explicit oracle 5	`[1353, 16807]`	`[1353, 16807]`	Passed
explicit oracle 6	`[4, 7]`	`[4, 7]`	Passed
explicit oracle 7	`[18, 49]`	`[18, 49]`	Passed

SHA-256 / 35ea38ea207b0fb7cdf3f32ea6c437c35cf79cf06f8d7032af2a52cfb397ed23

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

Case digest / bf1c7f0b314e0314c0b55564594fa6fc9bbf9d51b03a87da6b9d656960bd703d