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[1].
Proprietà matematiche
[modifica | modifica wikitesto]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
[modifica | modifica wikitesto]Sia dalla congettura di Dickson che dalla più ampia ipotesi H di Schinzel, entrambe ritenute vere dalla maggior parte dei matematici[2], seguirebbe che per ogni i esistono infinite catene di Cunningham di lunghezza i. Tuttavia, non sono conosciuti metodi diretti per generarne.
| 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[3].
Note
[modifica | modifica wikitesto]- ^ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998), pagina 290
- ^ (EN) Nicholas Anderson, Andrew J. Havens, Brian Hydefrost, Sean Murphy e Steve Sarasin, «Prime Numbers and the Riemann Hypothesis Archiviato il 15 giugno 2010 in Internet Archive.», pagina 6
- ^ a b (EN) Dirk Augustin, Cunningham Chain records.
Voci correlate
[modifica | modifica wikitesto]Collegamenti esterni
[modifica | modifica wikitesto]- (EN) The Prime Glossary: Cunningham chain, su primes.utm.edu.
- (EN) PrimeLinks++: Cunningham chain, su primes.utm.edu. URL consultato il 16 luglio 2003 (archiviato dall'url originale il 16 luglio 2003).
- (EN) Sequenza A005602, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.: primi termini delle più piccole catene di Cunningham del primo tipo di lunghezza n, per 1 ≤ n ≤ 14
- (EN) Sequenza A005603, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.: primi termini delle più piccole catene di Cunningham del secondo tipo di lunghezza n, per 1 ≤ n ≤ 15
