Cadena Cunningham

En matemáticas , una cadena de Cunningham es una secuencia determinada de números primos . Las cadenas de Cunningham reciben su nombre del matemático A. J. C. Cunningham . También se las conoce como cadenas de primos casi duplicados .

Una cadena de Cunningham de primer tipo de longitud n es una secuencia de números primos ( p ₁ , ..., p _n ) tal que p _{i +1}  =  2 p _i  +  1 para todo 1  ≤ i < n . (Por lo tanto, cada término de dicha cadena, excepto el último, es un primo de Sophie Germain , y cada término, excepto el primero, es un primo seguro ).   

Resulta que

${\displaystyle {\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}}}$

o, estableciendo${\displaystyle a={\frac {p_{1}+1}{2}}}$(el número${\displaystyle a}$no forma parte de la secuencia y no tiene por qué ser un número primo), tenemos${\displaystyle p_{i}=2^{i}a-1.}$

De manera similar, una cadena de Cunningham de segundo tipo de longitud n es una secuencia de números primos ( p ₁ , ..., p _n ) tal que p _{i +1}  =  2 p _i  −  1 para todo 1  ≤ i < n .   

De ello se deduce que el término general es

${\displaystyle p_{i}=2^{i-1}p_{1}-(2^{i-1}-1).}$

Ahora, al establecer${\displaystyle a={\frac {p_{1}-1}{2}}}$, tenemos${\displaystyle p_{i}=2^{i}a+1}$.

Las cadenas de Cunningham también se generalizan a veces a secuencias de números primos ( p ₁ , ..., p _n ) tales que p _{i +1} = ap _i + b para todo 1 ≤ i ≤ n para enteros coprimos fijos a y b ; las cadenas resultantes se denominan cadenas de Cunningham generalizadas .       

Una cadena de Cunningham se considera completa si no se puede extender más, es decir, si el término anterior y el siguiente de la cadena no son números primos.

Algunos ejemplos de cadenas Cunningham completas de primer tipo son las siguientes:

2, 5, 11, 23, 47 (El siguiente número sería 95, pero no es primo).

3, 7 (El siguiente número sería 15, pero no es primo).

29, 59 (El siguiente número sería 119, pero no es primo).

41, 83, 167 (El siguiente número sería 335, pero no es primo).

89, 179, 359, 719, 1439, 2879 (El siguiente número sería 5759, pero no es primo).

Algunos ejemplos de cadenas Cunningham completas de segundo tipo son los siguientes:

2, 3, 5 (El siguiente número sería 9, pero no es primo).

7, 13 (El siguiente número sería 25, pero no es primo).

19, 37, 73 (El siguiente número sería 145, pero no es primo).

31, 61 (El siguiente número sería 121 = 11² ^, pero no es primo).

Las cadenas de Cunningham ahora se consideran útiles en sistemas criptográficos ya que "proporcionan dos configuraciones adecuadas concurrentes para el criptosistema ElGamal ... [que] se puede implementar en cualquier campo donde el problema del logaritmo discreto sea difícil". ^{[ 1 ]}

De la conjetura de Dickson y de la hipótesis más amplia de Schinzel, H , ambas consideradas ciertas, se deduce que para cada k existen infinitas cadenas de Cunningham de longitud k . Sin embargo, no se conocen métodos directos para generar dichas cadenas.

Existen competiciones de computación para la cadena de Cunningham más larga o para la construida con los números primos más grandes, pero a diferencia del gran avance de Ben J. Green y Terence Tao —el teorema de Green-Tao , que establece que existen progresiones aritméticas de números primos de longitud arbitraria—, hasta la fecha no se conoce ningún resultado general sobre grandes cadenas de Cunningham.

q # denota el primordio 2 × 3 × 5 × 7 × ... × q .

A partir de 2018, la cadena Cunningham más larga conocida de cualquier tipo tiene una longitud de 19, descubierta por Jaroslaw Wroblewski en 2014. ^{[ 2 ]}

Sea el primo impar${\displaystyle p_{1}}$Sea el primer primo de una cadena de Cunningham de primera especie. El primer primo es impar, por lo tanto${\displaystyle p_{1}\equiv 1{\pmod {2}}}$Dado que cada primo sucesivo en la cadena es${\displaystyle p_{i+1}=2p_{i}+1}$resulta que${\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}}$. De este modo,${\displaystyle p_{2}\equiv 3{\pmod {4}}}$,${\displaystyle p_{3}\equiv 7{\pmod {8}}}$y así sucesivamente.

La propiedad anterior se puede observar informalmente considerando los números primos de una cadena en base 2. (Nótese que, como con todas las bases, multiplicar por la base "desplaza" los dígitos hacia la izquierda; por ejemplo, en decimal tenemos 314 × 10 = 3140). Cuando consideramos ${\displaystyle p_{i+1}=2p_{i}+1}$en base 2, vemos que, al multiplicar ${\displaystyle p_{i}}$por 2, el dígito menos significativo de ${\displaystyle p_{i}}$se convierte en el segundo dígito menos significativo de ${\displaystyle p_{i+1}}$. Porque${\displaystyle p_{i}}$es impar, es decir, el dígito menos significativo es 1 en base 2, sabemos que el segundo dígito menos significativo es 1 en base 2. ${\displaystyle p_{i+1}}$también es 1. Y, finalmente, podemos ver que ${\displaystyle p_{i+1}}$será impar debido a la adición de 1 a${\displaystyle 2p_{i}}$De esta forma, los números primos sucesivos en una cadena de Cunningham se desplazan esencialmente a la izquierda en binario, con unos ocupando los dígitos menos significativos. Por ejemplo, aquí hay una cadena completa de longitud 6 que comienza en 141361469:

Un resultado similar se aplica a las cadenas de Cunningham de segundo tipo. A partir de la observación de que${\displaystyle p_{1}\equiv 1{\pmod {2}}}$y la relación${\displaystyle p_{i+1}=2p_{i}-1}$resulta que${\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}}$En notación binaria, los números primos en una cadena de Cunningham de segundo tipo terminan con un patrón "0...01", donde, para cada${\displaystyle i}$, el número de ceros en el patrón para${\displaystyle p_{i+1}}$es uno más que el número de ceros para${\displaystyle p_{i}}$. Al igual que con las cadenas de Cunningham de primer tipo, los bits a la izquierda del patrón se desplazan una posición a la izquierda con cada primo sucesivo.

De manera similar, porque${\displaystyle p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,}$resulta que${\displaystyle p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}}$. Pero, según el pequeño teorema de Fermat ,${\displaystyle 2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}}$, entonces${\displaystyle p_{1}}$divide${\displaystyle p_{p_{1}}}$(es decir con${\displaystyle i=p_{1}}$). Por lo tanto, ninguna cadena de Cunningham puede tener una longitud infinita. ^{[ 3 ]}

• Primecoin , que utiliza cadenas Cunningham como sistema de prueba de trabajo.
• Cadena doble
• Números primos en progresión aritmética

• Glosario principal: Cadena de Cunningham
• Descubrimientos de Primecoin (primes.zone): base de datos en línea de hallazgos de primecoin con lista de registros y visualización.
• PrimeLinks++: Cadena Cunningham
• Secuencia OEIS A005602 (Prime más pequeño que inicia una cadena de Cunningham completa de longitud n (de primera especie)) -- el primer término de las cadenas de Cunningham completas más bajas de primera especie de longitud n , para 1 ≤ n ≤ 14       
• Secuencia OEIS A005603 (Cadenas de longitud n de primos casi duplicados) : el primer término de las cadenas de Cunningham completas más bajas de segundo tipo con longitud n , para 1 ≤ n ≤ 15