solution

Trong lược đồ chia sẻ bí mật Shamir ngưỡng $(k, n)$, bí mật $S$ được chọn làm hệ số tự do $f(0) \bmod p$ của một đa thức $f$ bậc $k-1$ trên trường $\mathbb{Z}_p$ ($p$ là số nguyên tố). Mỗi mảnh là một điểm $(x_i, y_i)$ với $y_i = f(x_i) \bmod p$ và $x_i \not\equiv 0 \pmod p$.

Cho đúng $k$ mảnh phân biệt (đủ để xác định duy nhất đa thức bậc $k-1$), hãy khôi phục bí mật $S = f(0) \bmod p$ bằng công thức nội suy Lagrange:

$f(0) = \sum_{i=1}^{k} y_i \prod_{j \ne i} \frac{-x_j}{x_i - x_j} \pmod p,$

trong đó phép chia được hiểu là nhân với nghịch đảo modulo $p$.

Ví dụ: với $p = 97, k = 2$ và hai điểm $(1, 55), (2, 68)$, đa thức là $f(x) = 42 + 13x$, bí mật là $f(0) = 42$.