Complexity
Rabin-Miller素數測試複雜度
我在考慮 Rabin-Miller 素性檢驗的複雜性。在維基百科上我找到 O(k log3n)，但沒有解釋。我的想法太簡單了。要查看 n 是否為素數，我們進行了 k 次嘗試，每次嘗試檢查第一個元素 b 是否為 1，否則我們在 b 序列中查找 -1。這裡 b = a^u mod n 和 n-1 = 2^l * u, u 奇數，與 (b,b^2^1,b^2^2,b^2^3,…,b^ 2^(l-1))。所以我假設在更壞的情況下，我們一直計算到最後一個指數，就在我們到達實際的 fermats-primetest 之前。因此，如果我們可以用 u 奇數表示 n-1 = 2^lu，那麼我們總共需要 k*(n-1)/(2u) 步。
通過使用指數的二進制展開 $ t $ 和重複平方你可以計算 $ x^t $ 模組 $ n $ 和 $ O(\log n) $ 模組 $ n $ 乘法運算。
並且每個模 $ n $ 乘法和除法將採取 $ O(\log^2 n) $ 整數運算。所以這使得 $ O(\log^3 n) $ 整數運算。
一旦你有 $ x^t $ 模組 $ n, $ 然後 $ x^{2t},x^{4t},x^{2^st} $ 模組 $ n $ 可以通過 $ s\leq \log_2 n $ 重複平方模的迭代 $ n $ .
所有其他操作都具有較低的複雜性。
如果你重複 $ k $ 次減少錯誤的機率，你得到 $ O(k \log^3 n). $
