Discrete-Logarithm
如何衡量離散對數問題的複雜度？
我看了這裡。答案基本上是說，要計算對數問題的複雜性，我們必須考慮代表組大小的數字的長度。看起來很隨意，為什麼我們不選擇組的大小作為參數呢？是否有一個標準可以知道選擇什麼論點？事實上，我知道我忽略了一些重要的事情，因為如果我們按照小組的規模來做，複雜性就會發生巨大的變化。所以請給我一個答案。
澄清一下：我想你問為什麼我們只考慮組大小的位長而不考慮組的實際大小來進行複雜性估計，至少這就是我試圖回答的問題。
為什麼我們不選擇組的大小作為參數？
我們的確是。
這完全取決於您要使用的約定。如果 $ q $ 是組的大小和 $ n\approx\log_2(q) $ （別忘了 $ 2^n\approx q $ ) 位長度，那麼您可以將蠻力所需的努力編寫為 $ \mathcal O(2^n) $ 或者 $ \mathcal O(q) $ ，第一個精度稍差（但不重要），第二個精度更高。然而，第一個很好地展示了所需的努力是如何呈指數增長的，而第二個可能會給您留下**線性的印象，此時人們可能會發現更難理解“這有多難，畢竟它只是線性增長”。
是否有一個標準可以知道選擇什麼論點？
基本上隨心所欲。如果您想清楚並知道您的聽眾無論如何都理解您的意思，請使用 $ q $ 否則使用 $ 2^n $ 使其更容易理解。