Prime-Numbers
給定 DSA 的 p 和 q，你如何證明它們是素數？
我被給
p = 4916335901 q = 88903並被要求證明這些是主要的以及
q|(p-1)在 DSA 中。我不確定如何做到這一點，究竟是什麼
q|(p-1)意思？
我被給 $ p = 4916335901 $ , $ q = 88903 $ 並被要求證明這些是主要的
檢查給定的整數是否 $ n $ 是素數，你必須檢查它是否只能被 $ 1 $ 和 $ n $ ，即它不是一個複合整數。如果給定這樣一個整數，您可以考慮給定整數，使用素數測試來檢查素數，或者如果數字如此小，只需詢問Wolfram alpha。在你的情況下，兩者 $ p $ 和 $ q $ 確實是素數，而你的給定 $ p $ 是形式 $ p=k\cdot q +1 $ . 大多數情況下，人們會遇到使用 $ k=2 $ ，密碼學中所謂的安全素數。您甚至可以有效地生成這樣的素數以用於加密目的。
也 $ q|(p-1) $ 在 DSA 中。
符號 $ a|b $ 意思是 $ a $ 均分 $ b $ ， IE， $ b $ 除以 $ a $ 餘數為零。這很容易通過計算來檢查 $ \frac{4916335901-1}{88903}=55300 $ ，所以是的 $ q|(p-1) $ .
使用形式的素數 $ p=k\cdot q+1 $ 與小 $ k $ , 你知道當你在 $ {\mathbb Z}_p^* $ （有秩序 $ p-1 $ ) 你有一個素數的循環子群 $ q $ .