形式的素數(2ķ)p+1(2ķ)p+1(2^k)p+1, 對於給定的素數ppp
讓 $ p $ 成為素數。（比如 256 位）
是否存在素數 $ q $ 這樣 $ q = (2^k)p + 1 $ , 對於一個大 $ k $ （類似於 256），如果它確實存在，有沒有辦法找出所有 $ k $ 這樣一個 $ q $ 存在。
[我知道它存在於 k =1，我正在尋找一個大 $ k $ ]
有數字證據表明，對於絕大多數素數 $ p $ ， 那裡存在 $ k $ 製造 $ q=2^k,p+1 $ 主要。請參閱A137715中的第一個例外。
我看到的唯一實用的方法是找到哪個 $ (p,k) $ 製作 $ q=2^k,p+1 $ 問題上下文中的主要內容是測試 $ q $ 使用快速測試的素數。如另一個答案中所述，篩選小素數可以在多個之間共享 $ k $ .
一個過於粗略的機率近似值 $ q=2^k,p+1 $ 是質數是相同大小的整數不能被任何一個整除的機率 $ 2 $ 也不是素數 $ p $ , 那是為了 $ p>2 $ 並大致由素數定理 $ \displaystyle\frac{2-2/p}{\ln(q)} $ , 我們可以近似為 $ \displaystyle\frac2{\ln(p)+k\ln(2)} $ 對於我們的大 $ p $ . 數值實驗表明，這是在正確的範圍內，但相當高。
更好的分析是對於隨機大素數 $ p $ , 和一個小素數 $ r>2 $ ， 數量 $ p\bmod r $ 大約是均勻分佈在 $ [1,r) $ ， 因此 $ 2^k,p\bmod r $ 也是，因此 $ q=2^k,p+1 $ 可以被 $ r $ 有機率 $ 1/(r-1) $ ， 而不是 $ 1/r $ 對於一個隨機整數。因此，它有助於將成為素數的機率降低一個因子 $ \frac{r-2}{r-1} $ 而不是 $ \frac{r-1}r $ . 我們可以糾正這種影響，產生 $$ \begin{align} \Pr(2^k,p+1\text{ is prime})&\approx\frac2{\ln(p)+k\ln(2)}\ \prod_{r\in\Bbb P,\ 2<r<\sqrt p}\frac{r,(r-2)}{(r-1)^2}\ &\approx\frac{2,C_2}{\ln(p)+k\ln(2)}\ \text{ with }C_2=0.66016\ldots \end{align} $$ 因為乘積很快收斂到孿生素數常數 $ C_2 $ （見A005597）。這種改進的近似對於大型 $ p $ 就像問題一樣。
我們開始估計找到素數的機率 $ 2^k,p+1 $ 對於給定的 $ p $ 和 $ k\in[k_0,k_1] $ 和 $ k_0 $ 和 $ k_1 $ 接近和相稱 $ \log_2(p) $ .
作為一個粗略的近似，我們可以假設得到一個素數的機率 $ k $ 獨立於 $ k $ , 並近似存在一個素數的機率 $ 2^k,p+1 $ 為了 $ k\in[k_0,k_1] $ 作為容易計算的 $$ 1-\prod_{k=k_0}^{k_1}\left(1-\frac{2,C_2}{\ln(p)+k\ln(2)}\right) $$
為了 $ p\approx 2^{256} $ , $ k\in[248,264] $ 給出一個機率 $ 0.061403\ldots $ ，這意味著我們需要測試大約一個 $ 16.286\ldots $ 素數 $ p $ 找到一個合適的¹。
這種近似可能會通過考慮到機率來改進 $ 2^k,p+1 $ 能被小素數整除 $ r $ 對於給定的 $ p $ 強烈依賴於 $ k $ ， 自從 $ 2^k\bmod r $ 是一個循環函式 $ k $ , 更糟的時期 $ (r-1)/s $ 經常與 $ s\ge2 $ （例如對於 $ r=7 $ ).
¹我通過實驗得到的結果很接近： $ \frac{3395526}{208621}=16.27\ldots $ 和 $ \frac{2116707}{130242}=16.25\ldots $ （掃描素數 $ p $ 從…開始 $ \left\lceil\frac7{22},\pi,2^{256}\right\rceil $ 和 $ \left\lceil\frac{113}{355},\pi,2^{256}\right\rceil $ ).