沙米爾秘密分享計劃的執行時間

讓 $ p>n $ 是一個素數。中的關鍵步驟 $ (t,n) $ 沙米爾的秘密分享如下：

經銷商步驟：

1. 選擇 $ s \in \mathbb{Z}_p^* $
2. 選擇 $ b_i \in \mathbb{Z}p^* $ 對於多項式 $ g(x)=s+\sum{i=1}^{t-1}b_ix^{i} $
3. 計算 $ s_i=f(i) \mod p $ /* 假使，假設 $ i $ 是參與者 $ P_i’s $ 公眾號*/
4. 相應地分配股份。

參與者步驟：

1. 應用拉格朗日多項式插值得到 s。

執行時間分析：

經銷商步驟：

1. $ O(1) $
2. $ O(t) $
3. $ O(t) $
4. $ O(t) $

參與者步驟：

1. $ O(t) $

對應步驟的執行時間是真的嗎？

所以，是整體時間複雜度 $ O(t) $ ?

我沒有在網際網路上找到任何討論 Shamir 秘密共享計劃的執行時間的地方。我的分析正確嗎？向我推薦任何來源或簡要解釋所涉及步驟的執行時間。

對應步驟的執行時間是真的嗎？

不。

• 必須執行莊家的第 3 步 $ n $ 每次執行的次數（每方一次） $ O(t) $ 時間。所以一定是 $ O(t\cdot n) $ .
• 經銷商需求的第4步 $ O(n) $ 將每一股分配給每一方。

我算 $ O(t\cdot n) $ 作為經銷商的整體時間複雜度。當然，你可以把它說得更具體一些，因為所有計算的時間取決於 $ p $ .

在本文中，部分 $ 1 $ 鑑於 Shamir 秘密共享方案的時間複雜度為 $ O(t log^2 t) $ ， 在哪裡 $ t $ 是門檻值。請再次查看此問題

引用自：https://crypto.stackexchange.com/questions/33240