尋找大的曲折素數
呼叫素數 $ p $ 狡猾的如果 $ (p-1)/2 $ 是一個卡邁克爾數。它們被稱為狡猾的，因為它們表面上看起來像安全素數，但實際上並非如此。特別是，使用這種素數的 Diffie-Hellman 可能容易受到Pohlig Hellman 算法的攻擊。
存在偏差素數。一個小例子是 $ 4931 $ . 一個更有趣的例子是
$$ 1947475860046218323 = 2(973737930023109161) + 1 = 2(220361)(1542521)(2864681) + 1. $$
這樣的素數肯定會出現在文獻中，但我的搜尋工作一直處於空白狀態，可能是因為它們被稱為其他東西（我只是為了這個問題的目的而創造了“狡猾的”）。有誰知道他們的參考資料？
我有興趣生成此類事物的大型範例。我所知道的用於生成大卡邁克爾數範例的主要工具（搜尋 $ k $ 為此 $ 6k+1, 12k+1, 18k+1 $ 都是素數，然後取他們的產品）似乎無法產生這樣的例子。假設存在大素數，那麼曲折素數無疑是極其罕見的，因此簡單地尋找它們並不是一個有前途的方法。在這個階段，我沒有想法。
使用 Chernick 表達式的問題 $ (6k+1)(12k+1)(18k+1) $ 它的概括是該數字始終與 1 mod 3 一致，因此兩倍的數字加一可以被素數整除，因此不是素數。然而，一切都沒有失去，Loh 和 Niebur 的方法“構造大卡邁克爾數的新算法”（啟發了著名的Alford、Granville 和 Pomerance “有無限多的卡邁克爾數”結果）可用於生成大卡邁克爾數這是 2 mod 3 並且有很多因素（使它們適合您的狡猾的應用程序）。
從 Loh 和 Niebur 的算法 C（第 285 頁）中得到啟發，我們添加了一些額外的小條件：
- 選擇素數的乘積 $ \Lambda\leftarrow 2^{h_1}q_2^{h_2}\cdots q_r^{h_r} $ 在哪裡 $ h_i $ 都是積極的，沒有一個 $ q_i $ 是 3。（如果 $ q_i $ 是小素數，所以取 $ q_2=5 $ , $ q_3=7 $ 等等都是不錯的選擇）。
- 全部測試 $ p(\alpha_1,\ldots,\alpha_r)\leftarrow 2^{\alpha_1}q_2^{\alpha_2}\cdots q_r^{\alpha_r}+1 $ 和 $ 0\le \alpha_i\le h_i $ 為素數。將成功的值收集到一個集合中 $ \mathcal S $ （省略 $ \Lambda+1 $ ）。您可能希望省略素數 3，以防假定的素數可被 3 整除有點明顯，或者因為它可能是費馬檢驗的基礎選擇。
- 計算 $ \prod_{p\in\mathcal S}\pmod\Lambda $ 並稱這個殘留物 $ s $ .
- 測試子集 $ \mathcal T\subset\mathcal S $ 其基數具有不同的奇偶性 $ \mathcal S $ 直到我們找到一個子集使得 $ \prod_{p\in\mathcal T}p\equiv s\pmod\Lambda $
- 放 $ N=\prod_{p\in\mathcal S\backslash\mathcal T}p $ . 這將是一個 Carmichael 數，它有奇數個素因數，並且與 2 mod 3 一致。
選擇應有足夠的多樣性 $ \mathcal T $ 得到一個適當大小的卡邁克爾數。然後，您可以乘以 2 並加 1。因為結果數是一致的 $ 3\pmod\Lambda $ , 它不能被任何素數整除 $ \Lambda $ 並且比平均水平要好得多（這很好）。