Catena di Cunningham
In teoria dei numeri, una catena di Cunningham (o catena di primi quasi raddoppiati) è una successione di numeri primi tale che:
- una catena di Cunningham del primo tipo di lunghezza n è una sequenza di primi (p1,...,pn) in cui per tutti gli 1 ≤ i < n, è valida la relazione pi+1 = 2pi + 1. Ogni termine di questo tipo di catena, tranne l'ultimo, è un numero primo di Sophie Germain, mentre ogni termine tranne il primo è un numero primo sicuro. Dato che ogni termine si ottiene aggiungendo uno al doppio del precedente, p2 = 2p1+1, p3 = 4p1+3, p4 = 8p1+7, ..., pi = 2i-1p1 + (2i-1-1).
- una catena di Cunningham del secondo tipo di lunghezza n è una sequenza di primi (p1,...,pn) in cui per tutti gli 1 ≤ i < n, è valida la relazione pi+1 = 2pi - 1.
- una catena di Cunningham generalizzata di lunghezza n è una sequenza di primi (p1,...,pn) in cui per tutti gli 1 ≤ i < n, è valida la relazione pi+1 = api ± b, dove a e b sono interi coprimi.
Le catene di Cunningham prendono il loro nome dal matematico Allan Cunningham. Una catena di Cunningham è detta completa se non può essere ulteriormente estesa, cioè se i numeri che verrebbero prima e dopo rispettivamente il primo e l'ultimo termine della successione non sono primi. Le catene di Cunningham sono considerate utili in crittografia, in quanto forniscono due impostazioni concorrenti per il sistema di cifratura ElGamal, che possono essere implementate dovunque sia difficile calcolare i logaritmi discreti.
Proprietà matematiche
Sia p1 il primo elemento di una catena di Cunningham del primo tipo. p1 è dispari, quindi è congruo ad 1 modulo 2. pi+1 = 2pi + 1, quindi pi ≡ 2i-1 (modulo 2i). Per esempio, p2 ≡ 3 (modulo 4); p3 ≡ 7 (modulo 8); p4 ≡ 15 (modulo 16); e così via.
Diverse proprietà delle catene di Cunningham possono essere comprese convertendo i numeri in base 2. Come in tutte le basi, moltiplicare un numero per il numero della base ha l'effetto di aggiungere una cifra 0 alla fine di quel numero. In questa base, moltiplicare per 2 e aggiungere 1 non equivale ad altro che aggiungere una cifra 1 alla fine del numero; similmente, moltiplicare per 2 un numero dispari e sottrarre 1 equivale ad aggiungere una cifra 0 nella penultima posizione del numero. Ecco una catena di Cunningham completa del primo tipo di lunghezza 6, in base 2 e base 10:
| Binario | Decimale |
| 1000011011010000000100111101 | 141361469 |
| 10000110110100000001001111011 | 282722939 |
| 100001101101000000010011110111 | 565445879 |
| 1000011011010000000100111101111 | 1130891759 |
| 10000110110100000001001111011111 | 2261783519 |
| 100001101101000000010011110111111 | 4523567039 |
Ed una del secondo tipo di lunghezza 5:
| Binario | Decimale |
| 10111111011 | 1531 |
| 101111110101 | 3061 |
| 1011111101001 | 6121 |
| 10111111010001 | 12241 |
| 101111110100001 | 24481 |
Uno stesso numero non può far parte sia di una catena del primo tipo che di una del secondo tipo, con le eccezioni di 2 e 3. Infatti, tutti gli altri numeri primi sono congrui ad 1 oppure a 5 modulo 6, ed è facile verificare che per tutti gli elementi pi di una catena del primo tipo deve valere pi ≡ 5 (modulo 6), mentre per quelli facenti parte di catene del secondo tipo deve valere pi ≡ 1 (modulo 6).
Catene di Cunningham più lunghe conosciute
Sia dalla congettura di Dickson che dalla più ampia ipotesi H di Schinzel, entrambe ritenute vere dalla maggior parte dei matematici, seguirebbe che per ogni i esistono infinite catene di Cunningham di lunghezza i. Tuttavia, non sono conosciuti metodi diretti per generarne.
Catene di Cunningham più grandi conosciute di lunghezza i )
| i | Tipo | p1 (primo elemento) | Numero di cifre | Anno | Scopritore |
| 1 | 1° | 243112609 − 1 | 12978189 | 2008 | GIMPS / Edson Smith |
| 2 | 1° | 183027×2265440 − 1 | 79911 | 2010 | T. Wu |
| 3 | 1° | 914546877×234772 − 1 | 10477 | 2010 | T. Wu |
| 4 | 1° | 119184698×5501# − 1 | 2354 | 2005 | J. Sun |
| 5 | 2° | 45008010405×2621# + 1 | 1116 | 2010 | D. Broadhurst |
| 6 | 1° | 37488065464×1483# − 1 | 633 | 2010 | D. Augustin |
| 7 | 1° | 162597166369×827# − 1 | 356 | 2010 | D. Augustin |
| 8 | 2° | 1148424905221×509# + 1 | 224 | 2010 | D. Augustin |
| 9 | 1° | 65728407627×431# − 1 | 185 | 2005 | D. Augustin |
| 10 | 2° | 1070828503293×239# + 1 | 109 | 2009 | D. Augustin |
| 11 | 2° | 2×13931865163581×127# + 1 | 63 | 2008 | D. Augustin |
| 12 | 2° | 13931865163581×127# + 1 | 62 | 2008 | D. Augustin |
| 13 | 1° | 1753286498051×71# − 1 | 39 | 2005 | D. Augustin |
| 14 | 2° | 335898524600734221050749906451371 | 33 | 2008 | J. K. Andersen |
| 15 | 2° | 28320350134887132315879689643841 | 32 | 2008 | J. Wroblewski |
| 16 | 2° | 2368823992523350998418445521 | 28 | 2008 | J. Wroblewski |
| 17 | 2° | 1302312696655394336638441 | 25 | 2008 | J. Wroblewski |
(dove p# sta per il primoriale di p: 2×3×5×7×...×p)
Al 2012, le catene di Cunningham più lunghe conosciute contano 17 elementi. La prima di questa lunghezza (del primo tipo, e il cui primo elemento è 2759832934171386593519) è stata scoperta nel 2008 da Jaroslaw Wroblewski, che successivamente ha anche scoperto diverse catene del secondo tipo con uguale lunghezza.
