GATE D30

Certified bounded modular square root: PARTIAL

partialEvidence I2Verify: doublePublic claim: No2026-07-20

What changed

The Phase 3 coupling reduces its useful computation to one exact problem: given an odd squarefree modulus with known factorization, a residue that is a square modulo every selected prime, and a bound, decide whether a bounded value squares to that residue. D30 studies exact algorithms and replayable certificates for that bounded modular square-root problem and delivers a certified hybrid evaluator. The evaluator returns exactly one of witness, empty-certified, open-incomplete, or invalid-input, with three exact paths, tiny root enumeration, meet-in-the-middle, and a q-scan, selected by a deterministic preflight dispatcher that picks the cheapest path whose certified count fits the caps and otherwise returns open at preflight without materializing state. Empty certificates carry a full structural completeness record, not a hash alone, and an independent backend replays them. On the complete finite domains all paths and the dispatcher agree with brute force. The approximately 109-prime useful instance returns open-incomplete at preflight, because the exact paths exceed the caps there. LRC(13) remains open.

Evidence

check 1Sign-vector CRT and interval formulations proved: bounded modular square root is a signed modular subset-sum on the nonzero prime factors, with an exact global-sign quotient. Two independent exact backends agree on every complete domain

check 2Certified hybrid evaluator: enumeration, meet-in-the-middle and q-scan under a deterministic preflight dispatcher; the approximately 109-prime instance returns open-incomplete at preflight without materializing state. V1 12/12, V2 8/8 independent, corruption 400/400

check 3D30-PARTIAL, evaluator PASS-HYBRID-EVALUATOR within its measured operating envelope; the target regime remains blocked-compute for the implemented exact paths, which is not a lower bound for all algorithms. No campaign authorized. LRC(13) OPEN

Verification: double · I2 · 12 artifacts (reports, verifiers, corruption suites, manifest with SHA-256)

← All gates