Naccache–Stern 背包密碼系統：如何計算ps−1一世反對pp一世s−1反對pp_i ^{s^{-1}} mod p?

在算法（連結）中，對於計算的 n 和選擇的密鑰 s，我們需要計算 $ \sqrt[s]{p_{i}} \bmod p $ .

作為原始研究論文（連結）中的一個例子，對於給定的 $ p=9700247 $ 和 $ s=5642069 $ , 給出 $ \sqrt[s]{2} \bmod p = 8567078 , \sqrt[s]{3} \bmod p = 5509479 $ 等等。

那麼如何計算這個 $ \sqrt[s]{p_{i}} \bmod p $ .

在 Naccache-Stern 背包密碼系統中，它認為 $ \gcd(s,p-1) = 1 $ . 因此，您可以計算 $ s $ 模組 $ p-1 $ （互質性確保了這種逆的存在）。計算這個逆可以使用擴展歐幾里得算法來完成，它為您提供 $ u,v $ 這樣 $ su + (p-1) v = 1 $ ： 作為 $ su = 1 \bmod p-1 $ , $ u $ 確實是相反的 $ s $ 模組 $ p-1 $ .

作為 $ p $ 是素數，其乘法子群有階 $ p-1 $ ， 因此 $ \sqrt[s]{p_i} \bmod p = p_i^{s^{-1} \bmod p-1} \bmod p = p_i^u \bmod p $ . 所以，一旦你計算了 $ u $ 從擴展歐幾里得算法，找到 $ s $ - 的根 $ p_i $ 模組 $ p $ 簡化為計算模冪。

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