尋找素數的算法qqq和ppp和q|p−1q|p−1q, |, p - 1?

我明白如果 $ p $ 那麼是素數 $ p-1 $ 必須是複合的（至少可以被 $ 2 $ 因為它是均勻的）。但是算法如何找到素數 $ q $ 這樣 $ q \cdot r = p - 1 $ . 我認為質因數分解是一個很難的問題？

能夠找到這樣的關鍵事實 $ p $ 在實踐中是：

• 使用諸如Miller-Rabin之類的素數檢驗，我們可以很容易地確定具有數千位的整數是否為素數，即使當它不是素數時我們通常無法分辨出它的所有因數。
• 關於 $ 1.4/b $ 的整數 $ b $ 位是素數。因此，隨機嘗試的可能性更大 $ b $ 的整數 $ b $ 位將發現一個素數（對於 $ b>4 $ ).

因此，一種可能的方法來找到一個有點隨機的大素數 $ p $ 有一些大的已知隨機素數 $ q $ 劃分 $ p-1 $ 是：

• 首先隨機選擇一個適當大的素數 $ q $

• 為連續 $ r $ 大小合適

  • 計算 $ p\gets q,r+1 $

  • 如果 $ p $ 是素數

    • 輸出 $ p $ 並停下來。

對此有一些改進。顯然，我們可以限制為 $ r $ . 這是一個特殊情況 $ s=2 $ 更一般的調整：對於任何小的素數 $ s $ ，它必須認為 $ q,r+1\bmod s\ne0 $ ， 因此 $ r\bmod s\ne-q^{-1}\bmod s $ . 這允許建立一個可能的篩子 $ r $ ，在沒有完整素性測試的情況下淘汰大多數候選人。

有標準化的算法來生成這樣的 $ p $ 和 $ q $ ，包括確定性地來自種子。請參閱FIPS 186-4 附錄 A.1

引用自：https://crypto.stackexchange.com/questions/72676