Randomness
均勻樣本大小的精確啟發式(Z/NZ)×(Z/ñZ)×(mathbb{Z} / N mathbb{Z})^times
我主要是一名數學家，涉足密碼學，我經常看到/聽到密碼學家使用均勻隨機樣本的啟發式方法 $ a $ 從 $ (\mathbb{Z} / N \mathbb{Z})^\times $ 將是“大”，或者 $ a \approx N $ , 未提及具體結果。
我想確保我理解這裡的精確啟發式。是一個精確的陳述，即均勻隨機樣本的期望值來自 $ (\mathbb{Z} / N \mathbb{Z})^\times $ 將會 $ N / 2 $ ，因此線性 $ N $ . 因此對於參數選擇（例如），如果我們可以選擇 $ N $ 並且安全性依賴於足夠大的均勻隨機樣本，我們可以使 $ N $ 足夠大以至於我們很有可能獲得足夠大的樣本？
甚至可以說更多。是的，在某些情況下，我們只關心這個數量是一個固定的正常數（比如 $ 1/2 $ ) 次 $ N $ .
雖然乘法組有大小 $ k:=\varphi(N) $ 大的仍然是真的 $ N $ （密碼學基於非常大的數字） $ k $ 通常非常接近 $ N. $ 例如，大部分 $ N $ 被選為素數（對於 Diffie Hellman，例如，當 $ k=N-1 $ ) 或 RSA 的兩個大小大致相等的大素數的乘積，在這種情況下$$ k=N(1-\frac{1}{p})(1-\frac{1}{q})\approx N(1-\frac{2}{\sqrt N}). $$所以平均值確實大約是 $ N/2 $ 出於所有實際目的。
此外，通常以以 2 為底的對數來測量該平均值，等於表示該數量所需的位數，在這種情況下， $ \log N $ 和 $ \log (N/2) $ 是微不足道的。
並且強度的度量，例如算法的複雜性，也是對數度量的，所以它們很好地結合在一起。