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.

Catene di Cunningham più grandi conosciute di lunghezza i [3])
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]

  1. ^ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998), pagina 290
  2. ^ (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
  3. ^ a b (EN) Dirk Augustin, Cunningham Chain records.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica