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 discretiJoe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998), pagina 290.
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 Nicholas Anderson, Andrew J. Havens, Brian Hydefrost, Sean Murphy e Steve Sarasin, «Prime Numbers and the Riemann Hypothesis », pagina 6, 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 Dirk Augustin, Cunningham Chain records.) 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.
Note
Voci correlate Numero primo di Sophie Germain Numero primo sicuro
Collegamenti esterni
: primi termini delle più piccole catene di Cunningham del primo tipo di lunghezza n, per 1 ≤ n ≤ 14 : primi termini delle più piccole catene di Cunningham del secondo tipo di lunghezza n, per 1 ≤ n ≤ 15
Categoria:Successioni di numeri primi