離散對數的 Pollard rho 的複雜性真的是模數嗎？
所以我到處都在閱讀 Pollard Rho for Dlog 的複雜性 $ g^a \pmod{n} $ 是 $ \mathcal O(\sqrt{n}) $ .
難道不應該 $ \mathcal{O}(\sqrt{q}) $ 和 $ q $ 的順序 $ g $ ?
Pollard-Rho 的複雜性確實是 $ O(\sqrt{\text{ord}(g)}) $ , 但即使 $ n $ 指模數，根據上下文，他們的陳述可能是正確的。如果在您的情況下考慮的模數是加密中的“經典”模數（例如 $ n = (2q+1)^k $ 為了一個素數 $ q $ 和一個小 $ k $ 等），因為通常會選擇模數，以便 ord $ (g) $ 很大， $ n = t\cdot \text{ord}(g) $ 對於一個小常數 $ t $ 所以 $ O(\sqrt{\text{ord}(g)}) = O(\sqrt{n}) $ .
它應該是 $ ;; O\Big(\hspace{-0.07 in}\sqrt{\text{order of g}}\hspace{-0.02 in}\Big) : $ 群冪 $ ;; $ .
什麼時候 $ q $ 是順序 $ g $ , 那將是 $ ;; O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{q}\hspace{-0.02 in}\right) : $ 群冪 $ ;; $ .
什麼時候 $ n $ 是順序 $ g $ , 那將是 $ ;; O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{n}\hspace{-0.02 in}\right) : $ 群冪 $ ;; $ .
他們還在使用嗎 $ n $ 為了
$$ the modulus from which one
takes the multiplicative group $$當他們寫 $ \hspace{.02 in}O\hspace{-0.04 in}\left(\hspace{-0.04 in}\sqrt{n}\hspace{-0.02 in}\right)\hspace{.02 in} $ ?