GATE D30

Căn bậc hai modular bị chặn chứng nhận: PARTIAL

partialEvidence I2Kiểm: doubleClaim công khai: Không2026-07-20

Điều gì thay đổi

Ghép Pha 3 rút gọn phần tính toán hữu ích của nó về một bài toán chính xác: cho một modulus lẻ squarefree với phân tích đã biết, một dư là bình phương modulo mọi prime đã chọn, và một chặn, quyết định liệu một giá trị bị chặn bình phương thành dư đó. D30 nghiên cứu thuật toán chính xác và chứng chỉ replay được cho bài toán căn bậc hai modular bị chặn đó và giao một bộ đánh giá hybrid chứng nhận. Bộ đánh giá trả đúng một trong witness, empty-certified, open-incomplete, hoặc invalid-input, với ba đường chính xác, liệt kê nghiệm nhỏ, meet-in-the-middle, và q-scan, chọn bởi một dispatcher preflight xác định lấy đường rẻ nhất mà đếm chứng nhận vừa cap và ngược lại trả open tại preflight mà không materialize trạng thái. Chứng chỉ empty mang bản ghi hoàn chỉnh cấu trúc đầy đủ, không phải chỉ một hash, và một backend độc lập replay chúng. Trên miền hữu hạn đầy đủ mọi đường và dispatcher khớp brute force. Thể hiện hữu ích khoảng 109 prime trả open-incomplete tại preflight, vì các đường chính xác vượt cap ở đó. LRC(13) vẫn mở.

Bằng chứng

kiểm 1Công thức sign-vector CRT và khoảng được chứng minh: căn bậc hai modular bị chặn là subset-sum modular có dấu trên các thừa số prime khác không, với thương global-sign chính xác. Hai backend chính xác độc lập khớp trên mọi miền đầy đủ

kiểm 2Bộ đánh giá hybrid chứng nhận: liệt kê, meet-in-the-middle và q-scan dưới dispatcher preflight xác định; thể hiện khoảng 109 prime trả open-incomplete tại preflight mà không materialize trạng thái. V1 12/12, V2 8/8 độc lập, corruption 400/400

kiểm 3D30-PARTIAL, evaluator PASS-HYBRID-EVALUATOR trong envelope vận hành đo được; miền mục tiêu vẫn blocked-compute cho các đường chính xác đã triển khai, không phải chặn dưới cho mọi thuật toán. Không chiến dịch được duyệt. LRC(13) MỞ

Kiểm chứng: double · I2 · 12 artifact (report, verifier, bộ tấn công, manifest SHA-256)

← Tất cả gate