Làm cách nào để tăng tốc độ tạo chia sẻ bí mật Shamir?

Giả sử chúng ta phải tạo chia sẻ bí mật của Shamir cho n điểm dữ liệu. Có cách nào để tăng tốc độ triển khai ngoài việc sử dụng quy tắc của Horner để đánh giá đa thức không?

Nếu bạn sử dụng thiết lập điển hình nơi chia sẻ $f(1), f(2),\ldots f(n)$ ở đâu $f(x)=c_kx^k+\cdots+c_0$ là một đa thức bậc $k$, sau đó bạn có thể sử dụng phép tính sai phân hữu hạn. Tạm thời bỏ qua bước khởi tạo

cho j=1,...,n 
    cập nhật f = (f + Deltaf[1]) mod p
    với i=1,..., k-1 
        cập nhật Deltaf[i] = (Deltaf[i] + Deltaf[i+1]) mod p
    xuất biến f dưới dạng f(j)
CHẤM DỨT

Vòng lặp chính mất $kn$ bổ sung và gia tăng (bạn có thể lưu $O(k^2)$ bổ sung nếu bạn cảm thấy thực sự keo kiệt) rất hiệu quả.

Giá trị ban đầu của $f$ Là $f(0)$. Các giá trị ban đầu của $\Delta^if$ có một chút lộn xộn: $\Delta^if(0)=i!\sum_{j=i}^kc_jS(j,i)$ ở đâu $S(j,i)$ là một Số Stirling loại hai. Ngoài ra, bạn có thể đánh giá đầu tiên $k$ điều khoản của $f$ và tính toán trực tiếp sự khác biệt được lặp đi lặp lại để tính toán tiếp theo $n-k$.