GATE D21
Tương thích chứng nhận thu hẹp theo chữ ký
Điều gì thay đổi
D20 bị chặn vì nó đòi toàn bộ vũ trụ phủ cục bộ không ràng buộc trước khi bất kỳ thông tin liên-prime nào thu hẹp truy vấn. D21 đảo ngược thứ tự: lan truyền một chữ ký toàn cục từng phần trước, rồi chỉ hỏi các phủ cục bộ tương thích với chữ ký đó. Hai sửa chữa và một thắng lợi kiến trúc dẫn dắt nó. Thứ nhất, sửa chữa padding: một phủ mười ba tốc độ đầy đủ là một lõi tối tiểu cộng một multiset padding, và padding không vô hại vì nó đổi bội, hệ số đối xứng, quỹ đạo xạ ảnh và tương thích CRT, nên oracle phải truy vấn trên toàn multiset mười ba, không chỉ lõi tối tiểu. Điều này được chứng minh và đối chiếu brute force. Thứ hai, oracle thu hẹp: khi cố định một chữ ký đích, multiset tốc độ bình phương bị ghim tới tác động scale thặng dư bình phương, nên mọi phủ khớp được tìm bằng cách quét nửa nhóm scale, chi phí tuyến tính theo prime thay vì liệt kê đầy đủ đã bị chặn. Đo trên các prime khó của D20 tới 2267, mỗi truy vấn thu hẹp kết thúc trong một phần giây với chứng chỉ replay được, đúng nơi đường cũ bị chặn. Mọi truy vấn vẫn trả về một trong matches-complete, empty-certified hoặc open-incomplete, một bác bỏ từ solver là vô hiệu nếu không có chứng minh máy-kiểm, và timeout là open. Ranh giới trung thực: bức tường liệt kê mỗi-truy-vấn đã gỡ, nhưng chiến dịch đầy đủ vẫn cần một seed gặp-nhau-ở-giữa tại prime đầu, nên chưa tuyên bố verdict chiến dịch. LRC(13) vẫn mở.
Bằng chứng
Kiểm chứng: double · I2 · 24 artifact (report, verifier, bộ tấn công, manifest SHA-256)