solution

Xét lược đồ chia sẻ bí mật Shamir ngưỡng $(k, n)$ trên $\mathbb{Z}_p$ ($p$ nguyên tố), nhưng được phát hành dư thừa: có $n > k$ mảnh $(x_1, y_1), \dots, (x_n, y_n)$ thay vì chỉ $k$ mảnh. Biết rằng nhiều nhất một trong số các mảnh từ vị trí $k+1$ đến $n$ có thể đã bị giả mạo (giá trị $y_i$ bị sửa sai), còn $k$ mảnh đầu tiên luôn đúng.

Hãy dùng $k$ mảnh đầu tiên để nội suy Lagrange, xác định duy nhất đa thức $f$ bậc $k-1$ sao cho $f(x_i) \equiv y_i \pmod p$ với $i=1,\dots,k$. Sau đó kiểm tra từng mảnh còn lại (vị trí $k+1$ đến $n$) có thỏa $f(x_i) \equiv y_i \pmod p$ hay không:

• Nếu tất cả đều thỏa mãn: in ra bí mật $S = f(0) \bmod p$.
• Nếu có đúng một mảnh không thỏa mãn (ở vị trí $m$, đánh số từ 1 theo thứ tự xuất hiện trong dữ liệu vào): in ra INVALID m.

Ví dụ: với $p=97, k=2, n=4$ và các mảnh $(1,63), (2,71), (3,79), (4,87)$: từ hai mảnh đầu suy ra $f(x) = 55 + 8x$; kiểm tra $f(3)=79$ và $f(4)=87$ đều khớp, nên bí mật là $55$.