草稿:坎寧安鏈

在數學中，坎寧安鏈（Cunningham chain）是指一串特定的質數序列，以艾倫·JC·坎寧安的名字命名。它們也被稱為近雙素數鏈。

定義

第一類長度是n的坎寧安鏈是(p₁, ..., p_n) 其中，對所有p_i+1 = 2p_i + 1 for all 1 ≤ i < n。 (因此，此鏈中除了第一項以外都是安全質數，除了最後一項以外都是索菲·熱爾曼質數)。

因此

${\begin{aligned}p_{2}&=2p_{1}+1,\\p_{3}&=4p_{1}+3,\\p_{4}&=8p_{1}+7,\\&{}\ \vdots \\p_{i}&=2^{i-1}p_{1}+(2^{i-1}-1),\end{aligned}}$

類似的，第二類長度是n的坎寧安鏈是(p₁, ..., p_n) 其中，對所有p_i+1 = 2p_i - 1 for all 1 ≤ i < n 。

因此

${\begin{aligned}p_{2}&=2p_{1}-1,\\p_{3}&=4p_{1}-3,\\p_{4}&=8p_{1}-7,\\&{}\ \vdots \\p_{i}&=2^{i-1}p_{1}-(2^{i-1}-1),\end{aligned}}$

範例

第一類的例子

• 2、5、11、23、47，下一項95不是質數
• 3、7，下一項15不是質數
• 29、59，下一項119不是質數
• 41、83、167，下一項335不是質數
• 89、179、359、719、1439、2879，下一項5759不是質數

第二類的例子

• 2、3、5，下一項9不是質數
• 7、13，下一項25不是質數
• 19、37、73，下一項145不是質數
• 31、61，下一項121不是質數

坎寧安鏈現在被認為在密碼系統中很有用，因為「它們為ElGamal加密算法提供了兩種離散對數困難的領域中實現」。

已知最長的坎寧安鏈

根據迪克森猜想和更廣泛的欣策爾假設H（兩者都被廣泛認為是正確的），可以得出對於每個k，都有無限多個長度為k的坎寧安鏈。然而，目前尚無已知的直接產生此類鏈的方法。

以下是最大已知的坎寧安鏈長度

長度	種類	質數	位數
1	（第一類/第二類）	2^136279841-1	41024320
2	第一類	2618163402417×2^1290000−1	388342
2	第二類	213778324725×2^561417+1	169015
3	第一類	1128330746865×2^66439−1	388342
3	第二類	214923707595×2^49073+1	169015

參見

• 算數數列中的質數

参考文献

Category:素數