找到兩個大（2048位）整數的最有效方法是什麼ķķk和qqq這樣p=kq_+1p=ķq+1p = kq + 1是素數，所以是qqq?

找到兩個大（2048位）整數的最有效方法是什麼 $ k $ 和 $ q $ 這樣 $ p = kq + 1 $ 是素數，所以是 $ q $ ?

有沒有我可以使用的標準算法？

你問的基本上是 DSA 參數生成（儘管有更大的 $ q $ ）。這在FIPS 186-4的 A.1 節中進行了描述。

從概念上講，素數生成僅僅是：生成一個隨機整數，看看它是否是素數，如果不是，則循環。在這種情況下，您將希望通過以下方式執行操作：

1. 生成一個隨機整數 $ q $ 預期大小（2048 位）。您需要確保它設置的最高位（因為您想要一個 2048 位整數，而不是 2047 位或更少的整數）。您還設置了底部位，以便 $ q $ 是奇數（如果是偶數則不是素數）。
2. 測試是否 $ q $ 是素數。如果不是，請返回步驟 1。正常的素性檢驗是Miller-Rabin。如果您使用現有的大整數庫，那麼它很可能已經提供了該測試。
3. 計算適當的範圍 $ k $ . 基本上，如果你想要決賽 $ p $ 長度正好為 4096 位，然後設置 $ k_l = \lceil (2^{4095} - 1) / q \rceil $ （分工 $ 2^{4095}-1 $ 經過 $ q $ ，四捨五入）和 $ k_h = \lfloor (2^{4096}-1) / q \rfloor $ （分工 $ 2^{4096}-1 $ 經過 $ q $ ，四捨五入低）。你需要 $ k $ 成為這樣 $ k_l \leq k \lt k_h $ .
4. 放 $ s = k_h - k_l $ .
5. 隨機生成 $ r $ 之間的整數 $ 0 $ （含）和 $ s $ 獨家的。一個好的方法是生成一個隨機的比特序列，大小為 $ s $ （即如果 $ s $ 長度為 2049 位，生成 2049 位）；生成的值不在範圍內，然後重試。這應確保範圍內的統一選擇。
6. 計算 $ k = r + k_l $ ， 然後 $ p = kq + 1 $ . 感謝如何 $ r $ 已生成，可以保證 $ p $ 有合適的尺寸。
7. 測試是否 $ p $ 是素數。如果不是，則循環到步驟 5。

這裡唯一的半智能就是曾經 $ q $ 已生成，您不必再次執行此操作。所以它只是兩個連續但不是嵌套的循環，一個 for $ q $ , 然後另一個 $ k $ .

在實踐中，找到一個隨機素數的複雜度介於 $ O(n^3) $ 和 $ O(n^4) $ （在哪裡 $ n $ 是素數的長度，以位為單位）（精確值取決於素數測試的編寫情況，特別是在避免對具有小素數的複合材料進行米勒-拉賓測試時）所以循環 $ p $ 平均而言，將比循環使用貴 8 到 16 倍 $ q $ .

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