Prime-Numbers
與因式分解相關的迭代平方的複雜性
在以下情況下，我遇到了一個處理
O(n) 位數的模乘數的問題：
給定兩個 n 位素數 p,q 定義 m=pq。 選擇一些’a’，以便 $ 2<a<m\hspace{-0.04 in}-\hspace{-0.04 in}2 $
並查看某個整數 t 的 a^(2^t)。 這是使用迭代平方來完成的。
該問題詢問在
不知道 m 的因式分解的情況和知道因式分解的情況下所需的模乘數。
該問題暗示使用 t 和 n 來量化事物。
我的問題是，m 的因式分解與此有什麼關係？
積分平方的技巧是使用 ab 的“on bits”（將它們稱為 bi for i: 0 -> n）通過將所有 (a^(2^i))^bi 相乘來計算 a^b。我不太明白這個問題的去向。
任何人都可以對事情有所了解嗎？
讓 $ m = pq $ . 計算 $ A := a^{2^t} \pmod m $ 需要 $ t $ $ 2n $ 位模乘法。
現在如果你知道分解 $ m $ （IE， $ p $ 和 $ q $ ) 然後你可以評估 $ A = a^{2^t} \pmod m $ 從 $ A_p := a^{2^t} \pmod p $ 和 $ A_q := a^{2^t} \pmod q $ 使用中文餘數：
$$ A = A_p + p\bigl[i_p (A_q-A_p) \bmod q\bigr]\quad\text{where $i_p = p^{-1} \bmod q$} $$ 的計算 $ A_p $ （分別 $ A_q $ ) 要求 $ t $ $ n $ 位模乘法。假如說 $ i_p $ 是預先計算的，計算 $ A $ 因此需要 $ (2t+1) $ $ n $ 位模乘法。