Dsa
DSA：如何計算 224 位qqq對於 2048 位ppp
$ p $ 是一個 2048 位素數
$ q $ 是一個 224 位素數
我知道 $ q $ 是的主要因數 $ p-1 $ ， 因此 $ p=1 \bmod q $ 但我無法編寫有效的程式碼來計算這一點。
- 我可以計算 2048 位素數 $ p $ ，但如何找到 $ q $ 有效率的？
目前我正在做的是生成 224 位素數並檢查它們是否正在劃分 $ p-1 $ 與否，但它需要永遠……
我可以計算 2048 位素數 $ p $ ，但如何找到 $ q $ 有效率的？
你做事的順序不對。
相反，您選擇 224 位 $ q $ , 然後是 2048 位素數的形式 $ p = kq + 1 $ （對於一些整數 $ k $ ).
這可以通過與找到 2048 位素數（無限制）基本相同的努力來完成，並直接回答問題，因為 $ p, q $ 對保證 $ p \equiv kq + 1 \equiv 1 \pmod q $