storia degli algoritmi per il calcolo dei numeri primi

Storia degli Algoritmi Numerici
UNIVERSITÀ DEGLI STUDI DI
NAPOLI “Parthenope”
Eseguito da: Nicola De Pasquale
Matr. TEC/R003
Relatore: prof. Francesca Perla
Anno Accademico 2004/05
1
Esiste una procedura per trovare
tutti i numeri primi?
• Al momento non si è trovato alcuna
procedura
• Si sa solo che i numeri primi sono infiniti,
siccome MCD(n; n+1)=1
2
Numeri primi
• Ogni numero N>1 o è primo, oppure è
prodotto di fattori primi distinti, ciascuno
preso col suo esponente;
• La scomposizione in fattori primi è unica, a
meno dell’ordine dei fattori.
3
Come trovare il Massimo
Comune Divisore tra due numeri
• MCD=?
• Mediante l’Algoritmo di Euclide,
• Eseguendo divisioni successive (tra numeri
interi) del tipo:
• a=bq+r, ponendo (per comodità) a>b>0.
4
Algoritmo di Euclide
•
•
•
•
•
•
•
• a=bq+r
Chiamando a=r-1, b=r0, r=r1 e q=q1, si ha:
Al primo passo: r-1=r0q1+r1;
Al secondo passo: r0=r1q2+r2;
Al terzo passo: r1=r2q3+r3;
Al penultimo passo: rn-2=rn-1qn+rn;
All’ultimo passo: rn-1=rnqn+1,
Perché rn+1=0, allora MCD(a;b)=rn.
5
Algoritmo di Euclide
• Riepilogando:
• MCD(a;b) è l’ultimo resto non nullo della
divisione iterativa tra i numeri a e b.
• In generale, si ha: ri-1=riqi+1+ri+1;
• Per i=0,…,n e con rn+1=0.
6
Algoritmo di Euclide
•
•
•
•
•
•
•
•
•
•
•
•
Esempio:
Trovare MCD(30030; 1224);
Mediante l’Algoritmo di Euclide si opera al seguente modo:
30030=1224.24+654;
1224=654.1+570;
654=570.1+84;
570=84.6+66;
84=66.1+18;
66=18.3+12;
18=12.1+6;
12=6.2+0, o meglio 12=6.2.
L’ultimo resto non nullo è 6, quindi 6=MCD(30030; 1224).
7
Crivello di Eratostene
• Dato un numero N, per verificare che esso
sia primo, basta che nessuno dei numeri
primi minori o uguali della parte intera della
sua radice quadrata divida N
• In simboli:
• N primo   p primo N : p/N
8
Crivello di Eratostene
• Eratostene è stato molto geniale, perché
mediante il suo algoritmo non è necessario
ricercare tra tutti i numeri N se il numero
N sia primo, ma solo in una parte più
piccola, selezionando così la ricerca dei
fattori che potrebbero scomporre il numero
o i numeri da noi cercati.
9
Crivello di Eratostene
• Esempio:
• Cercare tra i numeri 2 N100 quali sono primi:
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
10
Crivello di Eratostene
• Dapprima si segnano i numeri divisibili per 2
(escluso il numero 2 stesso):
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
11
Crivello di Eratostene
• Successivamente si segnano i numeri divisibili per
3 (escluso il numero 3 stesso) che non abbiamo
già tolto:
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
12
Crivello di Eratostene
• Dopodiché si segnano i numeri divisibili per 5
(escluso il numero 5 stesso) che non abbiamo già
tolto:
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
13
Crivello di Eratostene
• Al passo successivo si segnano i numeri divisibili
per 7 (escluso il numero 7 stesso) che non
abbiamo già tolto:
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
14
Crivello di Eratostene
• Ora potremmo fare la stessa operazione, per
il numero 11, ma non ha senso perché
100=10, e quindi 11>10=100, perché
tutti i fattori multipli di 11 che avremmo
dovuto eliminare (22, 33, 44, 55, 66, 77, 88,
99) sono già stati eliminati ai passi
precedenti;
• La stessa cosa vale per i numeri 13, 17, ecc.
15
Crivello di Eratostene
• Depennando i numeri multipli di 2, 3, 5 e 7
(esclusi i numeri 2, 3, 5 e 7), si ottengono
tutti i numeri primi 100
• Essi sono, quindi:
• 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 e
97.
16
Crivello di Eratostene
•
•
•
•
Esempio:
Provare se il numero 127 è primo:
127=11,269427…, e quindi 127=11
Occorre, perciò, cercare solo tra i numeri
primi 11, che sono: 2, 3, 5, 7 e 11;
• Dividere 127 per ciascuno di tali numeri;
• Se 127 non è multiplo di alcuno di questi
numeri, allora 127 è primo.
17
Crivello di Eratostene
•
•
•
•
•
•
127=63.2+1, quindi 127 non è divisibile per 2;
127=42.3+1, quindi 127 non è divisibile per 3;
127=25.5+2, quindi 127 non è divisibile per 5;
127=18.7+1, quindi 127 non è divisibile per 7;
127=11.11+6, quindi 127 non è divisibile per 11.
127 è quindi un numero primo non essendo
multiplo di alcuno di questi numeri primi.
18
Crivello di Eratostene
• In teoria il Crivello di Eratostene ci
permette di conoscere tutti i numeri primi,
perché operando di quadrato in quadrato si
trovano i numeri primi in quell’intervallo:
• Nel primo intervallo: 1<N2, si ha che 2 è
numero primo;
• Nel secondo intervallo: 2<N4, si ha che 3
è numero primo;
19
Crivello di Eratostene
• Nel terzo intervallo: 4<N16, si ha che 5, 7, 11 e
13 sono numeri primi;
• Nel quarto intervallo: 16<N256, si ha che 17, 19,
23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241 e 251 sono numeri primi;
20
Crivello di Eratostene
• Nel quinto intervallo ne troveremmo altri,
così come nel sesto, e così via.
• Tuttavia ad un certo punto ci dobbiamo
fermare da un lato perché i numeri primi
sono infiniti, dall’altro perché i calcoli con
un numero elevato di cifre sono difficili, se
non umanamente impossibili e, talvolta,
noiosi.
21
Distribuzione dei numeri primi
• Prima dell’avvento dei Computer le tavole
dei numeri primi impiegavano parecchie
pagine, oggi sono immagazzinate in forma
compatta.
• Si codificano i numeri dispari al seguente
modo:
• 0 se il numero è composto,
• 1 se il numero è primo.
22
Distribuzione dei numeri primi
• Esempio:
• Scrivo nella riga di sopra la tavola dei
numeri dispari da 1 a 50 e nella riga di sotto
sotto indico a seconda dei casi la cifra 0
oppure 1:
•
•
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0
23
Distribuzione dei numeri primi
• A questo punto ottengo le sequenze: 01110,
11011, 01001, 10010 e 11010
• Per semplicità di rappresentazione posso
eliminare da ciascuna delle sequenze
ottenute il termine centrale (quello multiplo
di 5)
• Ottengo così le sequenze: 0110, 1111, 0101,
1010 e 1110.
24
Distribuzione dei numeri primi
• Ciascuno dei numeri 0110, 1111, 0101,
1010 e 1110, può assumere un unico
carattere in base 16, ossia 6, F, 5, A, E.
• In questo modo sono descritti in forma
compatta i numeri primi.
25
Criteri di divisibilità
• Come si fa a sapere se un numero è
divisibile per un altro, senza effettuare la
divisione?
26
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
•
•
•
•
I criteri di divisibilità (in base 10) per alcuni numeri particolari sono facilmente esprimibili, o
vedendone l’ultima cifra, o sommando le cifre del numero o contando alternativamente le cifre del
numero, ne espongo alcuni semplici criteri.
Criterio di divisibilità per 2:
un numero è divisibile per due, se è pari; ossia se l’ultima cifra è pari; ovvero se l’ultima cifra è 0, 2,
4, 6, 8.
Criterio di divisibilità per 3:
un numero è divisibile per tre, se la somma delle sue cifre è ancora divisibile per tre.
Criterio di divisibilità per 5:
un numero è divisibile per cinque, se l’ultima sua cifra è 0 o 5.
Criterio di divisibilità per 9:
un numero è divisibile per nove, se la somma delle cifre è ancora multiplo di nove.
Criterio di divisibilità per 10:
un numero è divisibile per dieci, se l’ultima cifra è 0.
Criterio di divisibilità per 11:
un numero è divisibile per undici, se la somma delle cifre pari (a partire da destra) coincide con la
somma delle cifre dispari, e se ciò non si verifica, se la differenza tra le cifre pari del numero e le
cifre dispari è multiplo di undici.
27
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
•
•
Criteri di divisibilità (ricavabili dai criteri precedenti)
Criterio di divisibilità per 4:
un numero è divisibile per quattro, se le ultime due cifre (del numero) sono divisibili per
quattro, ossia se la penultima cifra è pari l’ultima cifra deve essere 0, 4 o 8, mentre se la
penultima cifra è dispari l’ultima cifra deve essere 2 o 6.
Criterio di divisibilità per 6:
un numero è divisibile per sei, se l’ultima sua cifra è pari e la somma delle sue cifre è
multiplo di tre.
Criterio di divisibilità per 8:
un numero è divisibile per otto, se le ultime tre cifre (del numero) sono divisibili per
otto.
Criterio di divisibilità per 12:
un numero è divisibile per dodici, se le ultime due sue cifre sono multiple di quattro e la
somma delle cifre del numero è multiplo di tre.
Criterio di divisibilità per 25:
un numero è divisibile per venticinque se le ultime due sue cifre sono 00, 25, 50 o 75.
28
Criteri di divisibilità
• Per le potenze di 2, 5 e 10 si hanno dei criteri di divisibilità che
valgono in generale:
• Criterio di divisibilità per 2k (ossia di una potenza di 2):
• un numero è divisibile per 2k, se le ultime k cifre sono multiple
di 2k.
• Criterio di divisibilità per 5h (ossia di una potenza di 5):
• un numero è divisibile per 5h, se le ultime h cifre sono multiple
di 5h.
• Criterio di divisibilità per 10n (ossia di una potenza di 10):
• un numero è divisibile per 10n, se le ultime n cifre sono tutte 0.
29
Criteri di divisibilità
• Talmud affermò che:
• Un numero della forma 100a+b è divisibile per 7
 un numero della forma 2a+b è divisibile per 7.
•
•
•
•
Esempio:
112=100.1+12;
14=2.1+12;
14 è divisibile per 7, quindi anche 112 lo è.
30
Criteri di divisibilità
• Secondo la matematica indiana:
• Un numero è divisibile per 9, se la somma
delle sue cifre è anch’essa divisibile per 9.
• Questo criterio di divisibilità è oggi detto
“prova del 9”
31
Criteri di divisibilità
• Fibonacci (1202):
Criteri di divisibilità per 7 e per 11.
• Talkis di Ibn al Banna (circa 1250):
Criteri di divisibilità per 7 e per 9.
• Nel XV secolo sono trovati criteri di
divisibilità per 7 e per 9 per la verifica di
operazioni aritmetiche.
32
Criteri di divisibilità
• Pierre Forcadel di Béziers (1556) affermò che:
• Scrivo il numero ed opero da sinistra verso destra.
• Moltiplico la prima cifra per 3 e sottraggo ad esso
il più grande multiplo di 7 ( del prodotto
ottenuto).
• Allora aggiungo al risultato la successiva cifra.
• Moltiplico di nuovo per 3, e così via.
• Se l’ultimo numero ottenuto è multiplo di 7, anche
il numero preso in considerazione lo è.
33
Criteri di divisibilità
• Esempio:
• Proviamo per il numero 5845:
• 5.3=15, 15-2.7=1, 1+8=9,
(a questo punto otteniamo il numero 945);
• 9.3=27, 27-3.7=6, 6+4=10,
(a questo punto otteniamo il numero 105);
• 10.3=30 30-4.7=2, 2+5=7.
• 7 è multiplo di 7, e quindi anche 5845 lo è.
34
Criteri di divisibilità
• Blaise Pascal (1654) raccoglie tutti i Criteri
di divisibilità, definendo una regola che vale
in generale (ne parlerò in seguito nello
specifico);
• Per sapere se un numero sia divisibile per p,
abbiamo bisogno di conoscere il resto della
divisioni delle varie potenze di 10 con p.
35
Criteri di divisibilità
• Fontanelle (1728) affermò che:
• Moltiplicando la prima cifra per 3, si
aggiunge, poi, ad essa la seconda cifra;
• Si sostituisce alle prime due cifre del
numero la loro somma;
• Continuando in questo modo, se l’ultimo
numero ricercato è 7, allora il numero è
divisibile per 7.
36
Criteri di divisibilità
• Esempio:
• Provo per il numero 16807, la sequenza dei
numeri ottenuta dai calcoli è:
• 16807, 9807, 3507, 1407, 707, 217, 77, 28,
14, 7.
• Essendo l’ultimo numero trovato 7, anche il
numero cercato: 16807 è divisibile per 7.
37
Criteri di divisibilità
•
•
•
•
•
Tucker (1889) affermò che:
Separando il numero in due parti, nelle quali:
Nella prima parte c’è tutto il numero, salvo l’ultima cifra;
Nella seconda parte c’è l’ultima cifra del numero.
Sottraggo alla prima parte del numero l’ultima cifra
moltiplicata per 2.
• Si prosegue nel calcolo, finché non restino solo le ultime
due cifre non siano multiple di 7.
• Se le ultime due cifre (ottenute nell’ultimo passaggio) sono
multiple di 7, anche il numero lo è.
38
Criteri di divisibilità
•
•
•
•
•
Esempio:
Partendo dal numero 2401, si ha:
240-2.1=238;
23-2.8=7.
7 è divisibile per 7, e quindi anche 2401 lo
è.
39
Criteri di divisibilità
• Blaise Pascal
• Criteri di divisibilità (in generale):
• Partendo dal criterio di divisibilità per 9,
indica un criterio valido anche per gli altri
numeri;
• Dandone anche una dimostrazione.
40
Criteri di divisibilità
• Dapprima sostituisce i numeri con le lettere
e moltiplica la cifra numerica per la sua
posizione, ossia per il resti di una potenza di
10 in quella base.
• Dopo aver operato questi prodotti basta
sommare le sue cifre e si può verificare in
tal modo la divisibilità.
41
Criteri di divisibilità
• Metodo di Pascal:
• Si scrive sulla stessa linea e in ordine
decrescente la sequenza dei numeri naturali,
in questo modo:
• 10 9 8 7 6 5 4 3 2 1
• K I H G F E D C B 1.
42
Criteri di divisibilità
• Dapprima scrivo la prima cifra e lo chiamo 1;
• Moltiplico questo numero (il numero 1) per 10 e
sottraggo il massimo intero multiplo di A (la base
della quale vorremmo conoscere la divisibilità)
che lo contiene, scrivo il resto, lo chiamo B e lo
metto sotto il numero 2;
• Moltiplico questo primo risultato (il numero B)
per 10 e sottraggo il massimo intero multiplo di A
che lo contiene, scrivo il resto, lo chiamo C e lo
metto sotto il numero 3;
43
Criteri di divisibilità
• Moltiplico questo primo risultato (il numero
C) per 10 e sottraggo il massimo intero
multiplo di A che lo contiene, scrivo il resto,
lo chiamo D e lo metto sotto il numero 4;
• E così via.
44
Criteri di divisibilità
•
•
•
•
•
•
•
Esempio
Scrivendo il numero TVNM, si opera così:
M.1
N.B
V.C
T.D
TVNM è divisibile per AM+NB+VC+TD è
divisibile per A
45
Criteri di divisibilità
• Criterio di divisibilità per 7:
• Scrivo nella prima riga i primi 10 numeri in
ordine decrescente e nella seconda riga i
resti delle di 10 in base 7,
• 10 9 8 7 6 5 4 3 2 1
• 6 2 3 1 5 4 6 2 3 1.
46
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
Per maggior chiarezza si ha:
Ad 1=100 corrisponde 1;
A 10 corrisponde 3, perché 10=1.7+3;
A 102 corrisponde 2, perché 100=14.7+2, o anche
30=4.7+2;
Al numero 103 corrisponde 6, perché 20=2.7+6;
Al numero 104 corrisponde 4, perché 60=8.7+4;
Al numero 105 corrisponde 3, perché 40=5.7+5;
Al numero 106 corrisponde 1, perché 50=7.7+1;
E così via, ritornando ai resti 1 3 2 6 4 5.
47
Criteri di divisibilità
• Esempio:
• Verifichiamo se il numero S=287542178 è
divisibile per 7.
• Scrivo le varie moltiplicazioni:
• 8.1=8; 7.3=21; 1.2=2; 2.6=12; 4.4=16;
5.5=25; 7.1=7; 8.3=14; 2.2=4.
• In seguito effettuo la somma:
• 8+21+2+12+16+25+7+24+4=119;
• Essendo 119 multiplo di 7, lo è anche il numero S.
48
Criteri di divisibilità
• Esempio:
• Verifichiamo se il numero Y=151996 è
divisibile per 37:
• Scrivo le varie moltiplicazioni:
• 6.1=6; 9.10=90; 9.26=234; 1.1=1;
5.10=50; 1.26=26.
• In seguito effettuo la somma:
• 6+90+234+1+50+26=407.
49
Criteri di divisibilità
• Il numero 407 è multiplo di 37, essendo
407=11.37.
• Quindi anche il numero Y è multiplo di 37.
50
Criteri di divisibilità
Un numero è divisibile per:
• 2, se l’ultima cifra è 0, 2, 4, 6 o 8;
• 3 (oppure 9), se la somma delle cifre è un
multiplo di 3 (oppure 9);
• 5, se l’ultima cifra è 0 o 5;
• 11, se la somma delle cifre pari meno la
somma delle cifre dispari del numero è
multiplo di 11
51
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
•
•
I resti delle potenze di 10 in base
(scrivo in parentesi gli elementi periodici):
2 sono 1 (0);
3 sono (1);
4 sono 1 2 (0);
5 sono 1 (0);
6 sono 1 (4);
7 sono (1 3 2 6 4 5);
8 sono 1 2 4 (0);
9 sono (1);
10 sono 1 (0);
52
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
•
•
I resti delle potenze di 10 in base
11 sono (1 10);
12 sono 1 10 (4);
13 sono (1 10 9 12 3 4);
14 sono 1 (10 2 6 4 12 8);
15 sono 1 (10);
16 sono 1 10 4 8 (0);
17 sono (1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12);
18 sono 1 (10);
19 sono (1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2);
20 sono 1 10 (0);
53
Criteri di divisibilità
•
•
•
•
I resti delle potenze di 10 in base
21 sono (1 10 16 13 4 19);
22 sono 1 (10 12);
23 sono (1 10 8 11 18 19 6 14 2 20 16 22 13 15 12
5 4 17 9 21 3 7);
• 24 sono 1 10 4 (16);
• 25 sono 1 10 (0);
• E così via.
54
Criteri di divisibilità
• Posso anche considerare le cifre
corrispondenti agli inversi dei numeri,
• Al fine di confrontare e collegare la
periodicità dei resti, la periodicità degli
inversi e i criteri di divisibilità;
• (scrivo in parentesi gli elementi periodici).
55
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
•
•
Gli inversi dei numeri sono:
1/2=0,5;
1/3=0,(3);
1/4=0,25;
1/5=0,2;
1/6=0,1(6);
1/7=0,(142857);
1/8=0,125;
1/9=0,(1);
1/10=0,1;
1/11=0,(09);
56
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
•
•
1/12=0,08(3);
1/13=0,(076923);
1/14=0,0(714285);
1/15=0,0(6);
1/16=0,0625;
1/17=0,(0588235294117647);
1/18=0,0(5);
1/19=0,(052631578947368421);
1/20=0,05;
1/21=0,(047619);
1/22=0,0(45);
57
Criteri di divisibilità
•
•
•
•
•
•
•
•
•
1/23=0,(0434782608695652173913);
1/24=0,041(6);
1/25=0,04;
1/26=0,0(384615);
1/27=0,(037);
1/28=0,03(571428);
1/29=0,(0344827586206896551724137931);
1/30=0,0(3);
E così via.
58
La teoria della congruenza
• Una diretta conseguenza del metodo di
Pascal è la teoria della congruenza:
• Sia A>1, esistono due interi a e b, con
a>b0, sono congrui modulo A, quando la
loro differenza a-b è un multiplo di A.
• E si scrive:
• ab(mod.A).
59
Confronto
• Come si può vedere, il numero degli
elementi periodici (ed aperiodici)
coincidono in entrambe le rappresentazioni,
quindi le due rappresentazioni sono
equivalenti per tutti i numeri, fissato una
dato sistema di numerazione.
60
La teoria della congruenza
• Se a=Aq+b è la divisione euclidea di a per
A, allora si ha:
• ab(mod.A).
61
La teoria della congruenza
• Proprietà usuali:
• 1) Se ab(mod.A) e bc(mod.A), allora
ac(mod.A).
• 2) Se ab(mod.A) e cd(mod.A), allora
a+cd+d(mod.A) acbd(mod.A).
62
La teoria della congruenza
• Tabella del resto ri in 10i=Aq+ri,
• Scrivendo sulla prima riga i numeri e nella
prima colonna i resti:
• 10 9 8 7 6 5 4 3 2 1
• r10 r9 r8 r7 r6 r5 r4 r3 r2 r1
63
La teoria della congruenza
• Essendo 10iri(mod.A), si ottengono i resti
per ricorrenza,
• Moltiplicando ambo i membri per 10, si ha:
10i+110ri(mod.A),
• Ossia ri+110ri(mod.A),
• N=an10n+ an-110n-1+…+ a110+ a0+ anrn+ an1ri-1+…+ a1r1+ a0(mod.A).
64
La teoria della congruenza
• Piccolo teorema di Fermat:
• Se p è un numero primo ed a è un intero che
non divide p, allora è vera l’equazione:
• ap-11(mod.p).
65
La teoria della congruenza
• La funzione φ(x) è tale che:
• Se x è un numero primo p, allora φ(p) = p-1
• Se x è potenza di numeri primi, ossia del
tipo pn, con n>1 e intero, allora φ(x) = (p-1)
. pn-1
• Se x è prodotto di due numeri primi distinti,
ossia del tipo p . q, allora φ(x) = (p-1) . (q-1)
66
La teoria della congruenza
• La funzione φ(x) è tale che, in generale:
• Se x = p1n .p2n .….pkn ,
• Allora φ(x) = φ(p1n .p2n .….pkn ) = φ(p1n ).
φ(p2n ).….φ(pkn ) = (p1-1).pn -1.(p2-1).pn -1 .….(pk1).pn -1
• O anche φ(x)= φ(p1n .p2n .….pkn ) = (p1-1).(p21).….(pk-1) . (p1n .p2n .….pkn ) / (p1.p2.….pk ),
• Che si può esprimere così:
• φ(x) = Π (pin ) = (pi-1) . φ(pin ) / (pi), con i=1,…,k.
1
2
k
1
2
2
k
k
1
1
2
k
1
1
i
2
2
k
k
i
67
La teoria della congruenza
• Equazione di Eulero (generalizzazione del
Piccolo teorema di Fermat):
• Se x è un numero intero>1 ed a è un altro
intero tale che MCD(x;a)=1, allora è vera
l’equazione:
• aφ(x)1(mod.x).
• Ovviamente per x=p siamo nelle ipotesi del
piccolo teorema di Fermat.
68
Residui quadratici
• Eulero (1754-55) definisce i residui quadratici.
• Calcolare se un numero x è o meno un residuo
quadratico modulo p è come risolvere l’equazione
• a2  x (mod. p).
• Ad esempio:
• 1, 2 e 4 sono residui quadratici modulo 7, mentre
3, 5 e 6 sono non-residui quadratici modulo 7.
• 1 e 4 sono residui quadratici modulo 5, mentre 2 e
3 sono non-residui quadratici modulo 5.
69
Residui quadratici
• Eulero (1783), ma senza dimostrazione e
Legendre (1785), ma con una dimostrazione
incompleta definiscono la legge di
reciprocità quadratica.
• Gauss (1810) dimostra la legge di
reciprocità quadratica, definendola il
gioiello dell’aritmetica.
70
Residui quadratici
• Se p non divide a, allora a(p-1)/21(mod.p).
• a è residuo quadraticoa(p-1)/21(mod.p);
• a è non residuo quadratico
a(p-1)/2p-1(mod.p).
71
Simbolo di Legendre
• Legendre impone a/p per il resto della
divisione di a(p-1)/2 per p.
• Si ha che(a/p)=1 se a è un residuo
quadratico modulo p;
• Mentre (a/p)=p-1 altrimenti.
72
Legge di reciprocità quadratica
• Siano p e q due numeri dispari,
• Se p e q sono entrambi della forma 4n+3, si
ha (p/q)=-(q/p);
• Se p e q non sono entrambi della forma
4n+3, si ha (p/q)=(q/p).
• In generale si ha: (p/q)(q/p)=(-1)(p-1)(q-1)/4.
73
I tre casi del simbolo di Legendre
• Se a è più grande di c, allora al posto di a, si scrive
il resto della divisione di a con c;
• Se il numero a, così ridotto, l’espressione (a/c)
cambierà (a seconda del resto di a e c mod.4) in
(c/a) o in –(c/a),
• si può ridurre (c/a) con (c’/a), dove c’ è il resto
della divisione di c con a;
• Se a non è primo, si può decomporre a nei suoi
singoli fattori primi: a=αβγ…, allora
(a/c)=(α/c)(β/c)(γ/c)…,
• in generale (α2/c)=(α/c)(α/c).
74
Test di primalità
• Sono vari i test per provare se un numero sia
primo o meno.
• I test sono basati su risultati elementari della teoria
della congruenza e della teoria dei residui
quadratici.
• Ne descrivo 3 di essi, data la loro importanza
storica.
• I primi due test richiedono la fattorizzazione di
N+1 o di N-1.
75
Test di primalità
• I test sulla primalità sono stati usati per scomporre
i numeri del tipo 2n±1, 10n1, e in generale an±1.
• In particolare i numeri di Fermat del tipo 2n+1,
con n=2k (col test di Pépin) e i numeri di
Mersenne del tipo 2n-1, con n=p (primo).
• Il “più grande numero primo conosciuto”,
aggiornando la ricerca al 1998, è un numero di
Mersenne, ossia 23021377-1, il quale possiede
909526 cifre.
76
L’inverso del Teorema di Fermat
• Richiamo del piccolo teorema di Fermat:
• Se a e p sono interi primi tra loro, allora
quando p è primo ap-11(mod.p).
• Ai cinesi era noto (500 a.C.) che se a=2,
allora 2p-2 era divisibile col primo p.
77
Fattorizzazione di
n
a -1
• Ogni numero primo è sempre un fattore del
precedente di una delle potenze di qualche
progressione, se l’esponente di questa
potenza è un divisore del precedente del
numero primo.
78
Fattorizzazione di
•
•
•
•
•
•
•
•
•
•
n
a -1
Esempi - Sia data la seguente progressione:
12 3 4 5 6
3 9 27 81 243 729 ecc.,
Con il suo esponente scritto sopra.
Prendo in considerazione il numero 13.
13 è un fattore di 26 = 33-1,
3 è uno dei fattori di 12, dove 12 = 13-1.
Siccome 6 (l’esponente di 729) è multiplo di 3,
Si ha che 13 è anche fattore di 728 = 36-1.
Questa proprietà è vera in generale per tutte le progressioni
e per tutti i numeri primi.
79
Numeri di Mersenne/Fermat
• Si può rappresentare (genericamente) un numero
in forma polinomiale, ossia:
• an-1.
• Se n=1, allora an-1=a-1;
• Se n=p (primo), allora an-1, ossia ap-1, e si può
scomporre in: ap-1=(a-1).(ap-1+ap-2+…+a+1);
• Se n=b.c (con b e c interi), allora an-1=abc-1 = (ab1).(ac-1+ac-2+…+a+1), o anche in:
• an-1=abc-1 = (ac-1).(ab-1+ab-2+…+a+1);
80
Numeri di Mersenne/Fermat
• In particolare se n è un numero pari, ossia n=2k,
allora:
• an-1=a2k-1=(a2k/2-1).(a2k/2+1)=(ak-1).(ak+1).
• In particolare, se a=2 ed n potenza di 2, si può
ottenere dalla scomposizione di un numero del
tipo di Mersenne, un numero del tipo di Fermat.
• Un numero del tipo ak+1 è sempre un caso
particolare di un numero del tipo an-1.
81
Scomposizioni polinomiali
• Dato un numero intero a>1, allora:
• an-1 = (a-1).(an-1+an-2+…+ a2+a+1), se n è un intero positivo qualsiasi.
• an-1 = ap-1 = (a-1).(ap-1+ap-2+…+ a2+a+1), con p numero primo, in tal
caso il secondo fattore non è ulteriormente scomponibile in Z[x].
• an+1 = (a+1).(an-1-an-2+…+ a2-a+1), se n è un intero positivo dispari.
• an+1 = ap+1 = (a+1).(ap-1-ap-2+…+ a2-a+1), con p numero primo
dispari, in tal caso il secondo fattore non è ulteriormente scomponibile
in Z[x].
• an-1 = (an/2-1).(an/2+1), se n è un numero intero positivo pari.
• an-1 = (abc-1) = (ab-1).(ac-1+ac-2+…+ a2+a+1), se n=bc.
• an+1 = (abc+1) = (ab+1).(ac-1-ac-2+…+ a2-a+1), se n è dispari ed n=bc.
82
Scomposizioni polinomiali
•
•
•
•
•
•
•
•
•
•
a1-1=a-1;
a2-1=(a-1).(a+1);
a3-1=(a-1).(a2+a+1);
a4-1=(a-1).(a+1).(a2+1);
a5-1=(a-1).(a4+a3+a2+a+1);
a6-1=(a-1).(a+1).(a2-a+1).(a2+a+1);
a7-1=(a-1).(a6+a5+a4+a3+a2+a+1);
a8-1=(a-1).(a+1).(a2+1).(a4+1);
a9-1=(a-1).(a2+a+1).(a6+a3+1);
a10-1=(a-1).(a+1).(a4-a3+a2-a+1).(a4+a3+a2+a+1);
83
Scomposizioni polinomiali
•
•
•
•
•
•
•
a11-1=(a-1).(a10+a9+a8+a7+a6+a5+a4+a3+a2+a+1);
a12-1=(a-1).(a+1).(a2+1).(a2-a+1).(a2+a+1).(a4+a2+1);
a13-1=(a-1).(a12+a11+a10+a9+a8+a7+a6+a5+a4+a3+a2+a+1);
a14-1=(a-1).(a+1).(a6-a5+a4-a3+a2-a+1).(a6+a5+a4+a3+a2+a+1);
a15-1=(a-1).(a2+a+1).(a4+a3+a2+a+1).(a8-a7+a5-a4+a3-a+1);
a16-1=(a-1).(a+1).(a2+1).(a4+1).(a8+1);
a17-1=(a-1).(a16+a15+a14+a13+a12+a11+a10+a9+a8+a7+a6+a5+a4+a3+a2+a+
+1);
• a18-1=(a-1).(a+1).(a2-a+1).(a2+a+1).(a6-a3+1).(a6+a3+1);
• a19-1=(a-1).(a18+a17+a16+a15+a14+a13+a12+a11+a10+a9+a8+ +a7+a6 +a5+
+a4+a3+a2+a+1);
• a20-1=(a-1).(a+1).(a2+1).(a4-a3+a2-a+1).(a4+a3+a2+a+1) ).(a8+a7+a6+ a5+
+a4+a3+a2+a+1);
84
Scomposizioni polinomiali
•
•
•
•
•
•
•
•
•
•
a21-1=(a-1).(a2+a+1).(a6+a5+a4+a3+a2+a+1).(a12-a11+a9-a8+a6-a4+a3-a+ +1);
a22-1=(a-1).(a+1).(a10+a9+a8+a7+a6+a5+a4+a3+a2+a+1).(a10-a9+a8-a7+a6-a5+a4a3+a2-a+ +1);
a23-1=(a-1).(a22+a21+a20+a19+a18+a17+a16+a15+a14+a13+a12+a11+a10+a9+
+a8+a7+a6+a5+a4+a3+a2+a+1);
a24-1=(a-1).(a+1).(a2+1).(a2-a+1).(a2+a+1).(a4+1).(a4+a2+1).(a8+a4+1);
a25-1=(a-1).(a4+a3+a2+a+1).(a20+a15+a10+a5+1);
a26-1=(a-1).(a+1) .(a12-a11+a10-a9+a8-a7+a6-a5+a4-a3+a2-a+1).(a12+a11+
+a10+a9+a8+a7+a6+a5+a4+a3+a2+a+1);
a27-1=(a-1).(a2+a+1).(a6+a3+1).(a18+a9+1);
a28-1=(a-1).(a+1).(a2+1).(a6-a5+a4-a3+a2-a+1).(a6+a5+a4+a3+a2+a+1).
.(a12+a10+a8+a6+a4+ +a2+1);
a29-1=(a-1).(a28+a27+a26+a25+a24+a23+a22+a21+a20+a19
a18+a17+a16+a15+a14+a13+a12+a11+ +a10+a9+a8+ +a7+a6 +a5+ +a4+a3+a2+a+1);
E così via.
85
Scomposizioni polinomiali
• Come detto prima, se p è primo, allora:
• (ap-1)/(a-1) = (ap-1+ap-2+…+a2+a+1)
• Non è ulteriormente scomponibile in forma
polinomiale, quindi:
• (an-1)/(a-1) è scomponibile in forma polinomiale
solo se n non è primo,
• Quindi (an-1)/(a-1) può essere un numero primo,
solo se n è primo, [ma non sempre risulta essere
un numero primo].
86
Numeri di Mersenne
•
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=1,
Si ha: (2-1)/(2-1) =1/1 = 1;
Ma 1 è un numero invertibile.
N.B.: d’ora in poi, essendo il denominatore
pari ad 1, verrà omesso nel calcolo.
87
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=2,
Si ha: (22-1)/(2-1) = 4-1 = 3;
Ma 3 è un numero primo.
88
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=3,
Si ha: (23-1)/(2-1) = 8-1 = 7:
Ma 7 è un numero primo.
89
Numeri di Mersenne
•
•
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=4,
Si ha: (24-1)/(2-1) = 16-1 = 15:
Ma 15 = 3 . 5, quindi è un numero composto.
Perché (24-1) è multiplo di (22-1) = 3.
N.B.: d’ora in poi, siccome è generale la
situazione che 2bc-1 sia multiplo di 2b-1, l’ultima
considerazione verrà omessa.
• Perché n numero composto => 2n-1 numero
composto.
90
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=5,
Si ha: (25-1)/(2-1) = 32-1 = 31:
Ma 31 è numero primo.
91
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=6,
Si ha: (26-1)/(2-1) = 64-1 = 63:
Ma 63 = 32 . 7, quindi è un numero
composto.
92
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=7,
Si ha: (27-1)/(2-1) = 127:
Ma 127 è un numero primo.
93
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=8,
Si ha: (28-1)/(2-1) = 255:
Ma 255 = 3 . 5 . 17, quindi è un numero
composto.
94
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=9,
Si ha: (29-1)/(2-1) = 511:
Ma 511 = 7 . 73, quindi è un numero
composto.
95
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=10,
Si ha: (210-1)/(2-1) = 1023:
Ma 1023 = 3 . 11 . 31, quindi è un numero
composto.
96
Numeri di Mersenne
•
•
•
•
Calcolo di (2n-1)/(2-1):
Se n=11,
Calcolo di (211-1)/(2-1) = 2047:
Il numero suddetto, a quanto sembra, dovrebbe
essere primo, perché 11, ossia n è primo, tuttavia
occorre provarlo.
• 2n-1 primo => n primo,
• Ma non vale il viceversa, come si può vedere nella
diapositiva successiva.
97
Numeri di Mersenne
• I numeri che possono dividere 211-1 sono solo quelli
del tipo 1+2.11k, con k numero intero positivo.
• I numeri di questo tipo sono i seguenti: 23, 45, 67, 89,
…, 22k+1, …;
• Di essi solo 23 e 45 possono essere presi in
considerazione, perché sono gli unici numeri
[2047]=45.
• 23 è un numero primo e 2047 : 23 = 89,
• Quindi 23 è un numero primo che divide 2047.
• Perciò 2047 non è primo, perché 2047 = 23 . 89.
98
Numeri di Mersenne
• In generale, alcuni numeri della forma:
• (2n-1)/(2-1)
• O meglio, siccome 2-1=1, della forma:
• 2n-1
• Sono descritti nella prossima diapositiva.
99
Scomposizione di 2n-1, al variare di n
1
1
2
3
3
7
4
3.5
5
31
6
32 . 7
7
127
8
3 . 5 . 17
9
7 . 73
10
3 . 11 . 31
11
23 . 89
12
32 . 5 . 7 . 13
13
8191
14
3 . 43 . 127
15
7 . 31 . 151
16
3 . 5 . 17 . 257
17
131071
18
33 . 7 . 19 . 73
19
524287
20
3 . 52 . 11 . 31 . 41
21
72 . 127 . 337
22
3 . 23 . 89 . 683
23
47 . 178481
24
32 . 5 . 7 . 13 . 17 . 241
25
31 . 601 . 1801
100
Scomposizione di 2n-1, al variare di n
26
3 . 2731 . 8191
27
7 . 73 . 262657
28
3 . 5 . 29 . 43 . 113 . 127
29
233 . 1103 . 2089
30
32 . 7 . 11 . 31 . 151 . 331
31
2147483647
32
3 . 5 . 17 . 257 . 65537
33
7 . 23 . 89 . 599479
34
3 . 43691 . 131071
35
31 . 71 . 127 . 122921
36
33 . 5 . 7 . 13 . 19 . 37 . 73 . 109
37
223 . 616318177
38
3 . 174763 . 524287
39
7 . 79 . 8191 . 121369
40
3 . 52 . 11. 17 . 31 . 41 . 61681
41
13367 . 164511353
42
32 . 72 . 43 . 127 . 337 . 5419
43
431 . 9719 . 2099863
44
3 . 5 . 23 . 89 . 397 . 683 . 2113
45
7 . 31 . 73 . 151 . 631 . 23311
46
3 . 47 . 178481 . 2796203
47
2351 . 4513 . 13264529
48
32 . 5 . 7 . 13 . 17 . 97 . 241 . 257 . 673
49
127 . 4432676798593
50
3 . 11 . 31 . 251 . 601. 1801 . 4051
101
Scomposizione di 2n-1, al variare di n
51
7 . 103 . 2143 . 11119 . 131071
52
3 . 5 . 53 . 157 . 1613 . 2731 . 8191
53
6361 . 1416003655831
54
34 . 7 . 19 . 73 . 87211 . 262657
55
23 . 31 . 89 . 881 . 3191 . 201961
56
3 . 5 . 17 . 29 . 43 . 113 . 127 . 15790321
57
7 . 524287 . 39268347319
58
3 . 59 . 233 . 1103 . 2089 . 3033169
59
179951 . 320343178337
60
32 . 52 . 7 . 11 . 13 . 31 . 41 . 61 . 151 . 331 . 1321
61
2305843009213693951
62
3 . 715827883 . 2147483647
63
72 . 73 . 127 . 337 . 92737 . 649657
64
3 . 5 . 17 . 257 . 641 . 65537 . 6700417
65
31 . 8191 . 145295143558111
66
32 . 7 . 23 . 67 . 89 . 683 . 20857 . 599479
67
193707721 . 761838257287
68
3 . 5 . 137 . 953 . 26137 . 43691 . 131071
69
7 . 47 . 178481 . 10052678938039
70
3 . 11 . 31 . 43 . 71 . 127 . 281 . 86171 . 122921
71
2361183241434822606847
72
33 . 5 . 7 . 13 . 17 . 19 . 37 . 73 . 109 . 241 . 433 . 38737
73
439 . 2298041 . 9361973132609
74
3 . 223 . 1777 . 21781083 . 616318177
75
7 . 31 . 151 . 601 . 1801 . 1065184428001
102
Scomposizione di 2n-1, al variare di n
76
3 . 5 . 229 . 457 . 174763 . 524287 . 525313
77
23 . 89 . 127 . 581283643249112959
78
32 . 7 . 79 . 2731 . 8191 . 121369 . 22366891
79
2687 . 224958284260258499201
80
3 . 52 . 11. 17 . 31 . 41 . 257 . 61681 . 4278255361
81
7 . 73 . 2593 . 262657 . 6947319183841
82
3 . 83 . 13367 . 164511353 . 8831418697
83
167 . 57912614113275649087721
84
32 . 5 . 72 . 13 . 29 . 43 . 113 . 127 . 337 . 1429 . 5419 . 14449
85
31 . 131071 . 9520972806333758431
86
3 . 431 . 9719 . 2099863 . 2932031007403
87
7 . 233 . 1103 . 2089 . 4177 . 9857737155463
88
3 . 5 . 17 . 23 . 89 . 353 . 397 . 683 . 2113 . 2931542417
89
61890019642690137449562111
90
33 . 7 . 11 . 19 . 31 . 73 . 151 . 331 . 631 . 23311 . 18837001
91
127 . 911 . 8191 . 2612585917490982161
92
3 . 5 . 47 . 277 . 1013 . 1657 . 30269 . 178481 . 2796203
93
7 . 2147483647 . 658812288653553079
94
3 . 283 . 2351 . 4513 . 13264529 . 165768537521
95
31 . 191 . 524287 . 12761021422289693921
96
32 . 5 . 7 . 13 . 17 . 97 . 193 . 241 . 257 . 673 . 65537 . 22253377
97
11447 . 13842607235828485645766393
98
3 . 43 . 127 . 4363953127297 . 4432676798593
99
7 . 23 . 73 . 89 . 199 . 599479 . 5079298981443391
100
3 . 53 . 11 . 31 . 41 . 101 . 251 . 601 . 1801 . 4051 . 8101 . 268501
103
Scomposizione di 2n-1, al variare di n
101
2535301200456458802993406410751
102
32 . 7 . 103 . 307 . 2143 . 2857 . 6529 . 11119 . 43691 . 131071
103
10141204801825835211973625643007
104
3 . 5 . 17 . 53 . 157 . 1613 . 2731 . 8191 . 264917625139441
105
72 . 31 . 71 . 127 . 151 . 337 . 122921 . 473474689919911
106
3 . 107 . 6361 . 1416003655831 . 28059810762433
107
162259276829213363391578010288127
108
34 . 5 . 7 . 13 . 19 . 37 . 73 . 109 . 87211 . 262657 . 68719214593
109
649037107316853453566312041152511
110
3 . 11 . 23 . 31 . 89 . 683 . 881 . 2971 . 3191 . 201961 . 538037401
111
7 . 223 . 616318177 . 2698495133088002829751
112
3 . 5 . 17 . 29 . 43 . 113 . 127 . 257 . 5153 . 15790321 . 54410972897
113
3391 . 23279 . 65993 . 1868569 . 1066818132868207
114
32 . 7 . 571 . 174763 . 524287 . 160465489 . 39268347319
115
31 . 47 . 14951 . 178481 . 10683848415441845139401
116
3 . 5 . 59 . 233 . 1103 . 2089 . 3033169 . 57646075230342349
117
7 . 73 . 79 . 937 . 6553 . 8191 . 121369 . 674274976909561
118
3 . 2833 . 179951 . 320343178337 . 67826891670011
119
127 . 239 . 131071 . 167056681047484447373134449
120
32 . 52 . 7 . 11 . 13 . 17 . 31 . 41 . 61 . 151 . 241 . 331 . 1321 . 61681 . 4562284561
121
23 . 89 . 727 . 178639878363164227858270210279
122
3 . 768614336404564651 . 2305843009213693951
123
7 . 13367 . 164511353 . 690814754065816531725751
124
3 . 5 . 5581 . 8681 . 715827883 . 2147483647 . 19037413721
125
31 . 601 . 1801 . 1267650638007162390353805312001
104
Scomposizione di 2n-1, al variare di n
126
33 . 72 . 19 . 43 . 73 . 127 . 337 . 5419 . 92737 . 649657 . 77158673929
127
170141183460469231731687303715884105727
128
3 . 5 . 17 . 257 . 641 . 65537 . 274177 . 6700417 . 67280421310721
…
…
156
32 . 7 . 5 . 132 . 79 . 157 . 313 . 1249 . 1613 . 2731 . 8191 . 21841 . 121369 . 22366891
…
…
193
13821503 . 61654440233248340616559 . 14732265321145317351353282383
…
…
204
32 . 5 . 7 . 13 . 103 . 137 . 307 . 409 . 953 . 2143 . 2857 . 3061 . 6529 . 11119 . 13669 . 26317 . 43691 . 131071 . 1326700741
…
…
256
3 . 5 . 17 . 257 . 641 . 65537 . 274177 . 6700417 . 67280421310721 . 59649589127497217 . 5704689200685129054721
257
535006138814359 . 1155685395246619182673033 . 374550598501810936581776630096313181393
…
…
512
3 . 5 . 17 . 257 . 641 . 65537 . 274177 . 6700417 . 67280421310721 . 59649589127497217 . 5704689200685129054721 .
1238926361552897 . 93461639715357277769163558199606896584051237541638188580280321
…
…
521
1372959532026121942996380159816278643453887060028661081878892691837108636679531210424511928132290910
9954592622782961716074243975999433287625148056582230114303
E così via
105
Scomposizione di 3n-1, al variare di n
1
2
2
23
3
2 . 13
4
24 . 5
5
2 . 112
6
23 . 7 . 13
7
2 . 1093
8
25 . 5 . 41
9
2 . 13 . 757
10
23 . 112 . 61
11
2 . 23 . 3851
12
24 . 5 . 7 . 13 . 73
13
2 . 797161
14
23 . 547 . 1093
15
2 . 112 . 13 . 4561
16
26 . 5 . 17 . 41 . 193
17
2 . 1871 . 34511
18
23 . 7 . 13 . 19 . 37 . 757
19
2 . 581130733
20
24 . 52 . 112 . 61 . 1181
21
2 . 13 . 1093 . 368089
22
23 . 23 . 67 . 661 . 3851
23
2 . 47 . 1001523179
24
25 . 5 . 7 . 13 . 41 . 73 . 6481
25
2 . 112 . 3501192601
106
Scomposizione di 3n-1, al variare di n
26
23 . 797161 . 398581
27
2 . 13 . 109 . 433 . 757 . 8209
28
24 . 5 . 29 . 547 . 1093 . 16493
29
2 . 59 . 581613367499
30
23 . 7 . 112 . 13 . 31 . 61 . 271 . 4561
31
2 . 308836698141973
32
27 . 5 . 17 . 41 . 193 . 21523661
33
2 . 13 . 23 . 3851 . 2413941289
34
23 . 103 . 307 . 1021 . 64570081
35
2 . 112 . 1093 . 189150889201
36
24 . 5 . 7 . 13 . 19 . 37 . 73 . 757 . 530713
37
2 . 225141952945498681
38
23 . 581130733 . 290565367
39
2 . 132 . 797161 . 15040635637
40
25 . 52 . 112 . 41 . 61 . 1181 . 42521761
41
2 . 18236498188585393201
42
23 . 72 . 13 . 43 . 547 . 1093 . 2269 . 368089
43
2 . 164128483697268538813
44
24 . 5 . 23 . 67 . 661 . 3851 . 3138105961
45
2 . 112 . 13 . 757 . 4561 . 271983020401
46
23 . 47 . 1001523179 . 23535794707
47
2 . 13294407179478751643893
48
26 . 5 . 7 . 13 . 41 . 73 . 193 . 6481 . 731682737
49
2 . 1093 . 109469043563868952237
50
23 . 112 . 61 . 3501192601 . 3472494301
107
Scomposizione di 4n-1, al variare di n
1
3
2
3.5
3
32 . 7
4
3 . 5 . 17
5
3 . 11 . 31
6
32 . 5 . 7 . 13
7
3 . 43 . 127
8
3 . 5 . 17 . 257
9
33 . 7 . 19 . 73
10
3 . 52 . 11 . 31 . 41
11
3 . 23 . 89 . 683
12
32 . 5 . 7 . 13 . 17 . 241
13
3 . 2731 . 8191
14
3 . 5 . 29 . 43 . 113 . 127
15
32 . 7 . 11 . 31 . 151 . 331
16
3 . 5 . 17 . 257 . 65537
17
3 . 43691 . 131071
18
33 . 5 . 7 . 13 . 19 . 37 . 73 . 109
19
3 . 174763 . 524287
20
3 . 52 . 11. 17 . 31 . 41 . 61681
21
32 . 72 . 43 . 127 . 337 . 5419
22
3 . 5 . 23 . 89 . 397 . 683 . 2113
23
3 . 47 . 178481 . 2796203
24
32 . 5 . 7 . 13 . 17 . 97 . 241 . 257 . 673
25
3 . 11 . 31 . 251 . 601 . 1801 . 4051
108
Scomposizione di 4n-1, al variare di n
26
3 . 5 . 53 . 157 . 1613 . 2731 . 8191
27
34 . 7 . 19 . 73 . 87211 . 262657
28
3 . 5 . 17 . 29 . 43 . 113 . 127 . 15790321
29
3 . 59 . 233 . 1103 . 2089 . 3033169
30
32 . 52 . 7 . 11 . 13 . 31 . 41 . 61 . 151 . 331 . 1321
31
3 . 715827883 . 2147483647
32
3 . 5 . 17 . 257 . 641 . 65537 . 6700417
33
32 . 7 . 23 . 67 . 89 . 683 . 20857 . 599479
34
3 . 5 . 137 . 953 . 26137 . 43691 . 131071
35
3 . 11 . 31 . 43 . 71 . 127 . 281 . 86171 . 122921
36
33 . 5 . 7 . 13 . 17 . 19 . 37 . 73 . 109 . 241 . 433 . 38737
37
3 . 223 . 1777 . 21781083 . 616318177
38
3 . 5 . 229 . 457 . 174763 . 524287 . 525313
39
32 . 7 . 79 . 2731 . 8191 . 121369 . 22366891
40
3 . 52 . 11. 17 . 31 . 41 . 257 . 61681 . 4278255361
41
3 . 83 . 13367 . 164511353 . 8831418697
42
32 . 5 . 72 . 13 . 29 . 43 . 113 . 127 . 337 . 1429 . 5419 . 14449
43
3 . 431 . 9719 . 2099863 . 2932031007403
44
3 . 5 . 17 . 23 . 89 . 353 . 397 . 683 . 2113 . 2931542417
45
33 . 7 . 11 . 19 . 31 . 73 . 151 . 331 . 631 . 23311 . 18837001
46
3 . 5 . 47 . 277 . 1013 . 1657 . 30269 . 178481 . 2796203
47
3 . 283 . 2351 . 4513 . 13264529 . 165768537521
48
32 . 5 . 7 . 13 . 17 . 97 . 193 . 241 . 257 . 673 . 65537 . 22253377
49
3 . 43 . 127 . 4363953127297 . 4432676798593
50
3 . 53 . 11 . 31 . 41 . 101 . 251 . 601 . 1801 . 4051 . 8101 . 268501
109
Scomposizione di 5n-1, al variare di n
1
22
2
23 . 3
3
22 . 31
4
24 . 3 . 13
5
22 . 11 . 71
6
23 . 32 . 7 . 13
7
22 . 19531
8
25 . 3 . 13 . 313
9
22 . 19 . 31 . 829
10
23 . 3 . 11 . 71 . 521
11
22 . 12207031
12
24 . 32 . 7 . 13 . 31 . 601
13
22 . 305175781
14
23 . 5 . 29 . 449 . 19531
15
22 . 11 . 31 . 71 . 181 . 1741
16
26 . 3 . 13 . 17 . 313 . 11489
17
22 . 190734863281
18
23 . 33 . 7 . 19 . 31 . 829 . 5167
19
22 . 4788371582031
20
24 . 3 . 11. 13 . 41 . 71 . 521 . 9161
21
22 . 31 . 19531 . 196890121
22
23 . 3 . 23 . 67 . 5281 . 12207031
23
22 . 2980232238769531
24
25 . 32 . 7 . 13 . 31 . 313 . 601 . 390001
25
22 . 11 . 71 . 101 . 251 . 401 . 9384251
110
Scomposizione di 6n-1, al variare di n
1
5
2
5.7
3
5 . 43
4
5 . 7 . 37
5
52 . 311
6
5 . 7 . 31 . 43
7
5 . 55987
8
5 . 7 . 37 . 1297
9
5 . 19 . 43 . 2467
10
52 . 7 . 11 . 101 . 311
11
5 . 72559411
12
5 . 7 . 13 . 31 . 37 . 43 . 97
13
5 . 2612138803
14
5 . 7 . 29 . 1379 . 55987
15
52 . 43 . 311 . 1406371
16
5 . 7 . 37 . 1297 . 1679617
17
5 . 3385331888947
18
5 . 7 . 19 . 31 . 43 . 2467 . 46441
19
5 . 121871948002099
20
52 . 7 . 11. 37 . 101 . 311 . 1634221
21
5 . 43 . 55987 . 1822428931
22
5 . 7 . 51828151 . 72559411
23
5 . 157946044610720563
24
5 . 7 . 13 . 31 . 37 . 43 . 97 . 1297 . 1678321
25
53 . 311 . 731325737104301
111
Scomposizione di 7n-1, al variare di n
1
2.3
2
24 . 3
3
2 . 32 . 19
4
25 . 3 . 52
5
2 . 3 . 2801
6
24 . 32 . 19 . 43
7
2 . 3 . 29 . 4733
8
26 . 3 . 52 . 1201
9
2 . 33 . 19 . 37 . 1063
10
2 . 3 . 11 . 191 . 2801
11
2 . 3 . 1123 . 293459
12
25 . 32 . 52 . 13 . 19 . 43 . 181
112
Scomposizione di 8n-1, al variare di n
1
7
2
32 . 7
3
7 . 73
4
32 . 5 . 7 . 13
5
7 . 31 . 151
6
33 . 7 . 19 . 73
7
72 . 127 . 337
8
32 . 5 . 7 . 13 . 17 . 241
9
7 . 73 . 262657
10
32 . 7 . 11 . 31 . 151 . 331
11
7 . 23 . 89 . 599479
12
33 . 5 . 7 . 13 . 19 . 37 . 73 . 109
13
7 . 79 . 8191 . 121369
14
32 . 72 . 43 . 127 . 337 . 5419
15
7 . 31 . 73 . 151 . 631 . 23311
16
32 . 5 . 7 . 13 . 17 . 97 . 241 . 257 . 673
17
7 . 103 . 2143 . 11119 . 131071
18
34 . 7 . 19 . 73 . 87211 . 262657
19
7 . 524287 . 39268347319
20
32 . 52 . 7 . 11 . 13 . 31 . 41 . 61 . 151 . 331 . 1321
21
72 . 73 . 127 . 337 . 92737 . 649657
22
32 . 7 . 23 . 67 . 89 . 683 . 20857 . 599479
23
7 . 47 . 178481 . 10052678938039
24
33 . 5 . 7 . 13 . 17 . 19 . 37 . 73 . 109 . 241 . 433 . 38737
25
7 . 31 . 151 . 601 . 1801 . 1065184428001
113
Scomposizione di 9n-1, al variare di n
1
23
2
24 . 5
3
23 . 7 . 13
4
25 . 5 . 41
5
23 . 112 . 61
6
24 . 5 . 7 . 13 . 73
7
23 . 547 . 1093
8
26 . 5 . 17 . 41 . 193
9
23 . 7 . 13 . 19 . 37 . 757
10
24 . 52 . 112 . 61 . 1181
11
23 . 23 . 67 . 661 . 3851
12
25 . 5 . 7 . 13 . 41 . 73 . 6481
13
23 . 398581 . 797161
14
24 . 5 . 29 . 547 . 1093 . 16493
15
23 . 7 . 112 . 13 . 31 . 61 . 271 . 4561
16
27 . 5 . 17 . 41 . 193 . 21523661
17
23 . 103 . 307 . 1021 . 64570081
18
24 . 5 . 7 . 13 . 19 . 37 . 73 . 757 . 530713
19
23 . 581130733 . 290565367
20
25 . 52 . 112 . 41 . 61 . 1181 . 42521761
21
23 . 72 . 13 . 43 . 547 . 1093 . 2269 . 368089
22
24 . 5 . 23 . 67 . 661 . 3851 . 3138105961
23
23 . 47 . 1001523179 . 23535794707
24
26 . 5 . 7 . 13 . 41 . 73 . 193 . 6481 . 731682737
25
23 . 112 . 61 . 3501192601 . 3472494301
114
Scomposizione di 10n-1, al variare di n
1
32
2
32 . 11
3
33 . 37
4
32 . 11 . 101
5
32 . 41 . 271
6
33 . 7 . 11 . 13 . 37
7
32 . 239 . 4649
8
32 . 11 . 73 . 101 . 137
9
34 . 37 . 333667
10
32 . 11 . 41 . 271 . 9091
11
32 . 11111111111
12
33 . 7 . 11 . 13 . 37 . 101 . 9901
13
32 . 53 . 79 . 265371653
14
32 . 11 . 239 . 4649 . 909091
15
33 . 37 . 41 . 271 . 90090991
16
32 . 11 . 17 . 73 . 101 . 137 . 5882353
17
32 . 11111111111111111
18
34 . 7 . 11 . 13 . 19 . 37 . 52579 . 333667
19
32 . 1111111111111111111
20
32 . 11 . 41. 101 . 271 . 9091 . 99009901
21
33 . 37 . 43 . 239 . 4649 . 20951185837
22
32 . 112 . 23 . 35932447 . 11111111111
23
32 . 11111111111111111111111
24
32 . 7 . 11 . 13 . 37 . 73 . 101 . 137 . 9901 . 99990001
25
32 . 41 . 271 . 100001000010000100001
115
Inverso del Teorema di Fermat
• Il Teorema di Fermat ci permette di stabilire
se un numero è composto.
• Il Teorema di Fermat non serve per stabilire
se un numero è primo.
• Quindi, l’Inverso del Teorema di Fermat è
falso, come mostro in un controesempio
nella prossima diapositiva.
116
Inverso del Teorema di Fermat
•
•
•
•
•
•
•
•
•
•
•
Esempio:
Per a=2 e N=341, si ha 23401(mod.341),
341 non è primo, ma è il prodotto di 11 per 31.
Dimostrazione:
Siccome le successive potenze di 2 in base 11 sono:
{2, 4, 8, 5, 10, 9, 7, 3, 6, 1}, si ha:
2101(mod.11),
E, in particolare, essendo 340 multiplo di 10, si ha anche:
• 23401(mod.11),
perché le successive potenze di 2 in base 31 sono:
{2, 4, 8, 16, 1}, si ha:
• 251(mod.31),
E, in particolare, essendo 340 multiplo di 5, si ha anche:
• 23401(mod.31);
Quindi, si ha alla fine che: 23401(mod.[11.31]), o per meglio dire:
• 23401(mod.341).
117
Inverso del Teorema di Fermat
•
•
•
•
•
•
•
•
•
•
Esempio:
Per a=3 e N=341, allora 334056(mod.341).
Dimostrazione:
Le successive potenze di 3 in base 341 fino ad arrivare ad 1 sono: {3,
9, 27, 81, 243, 47, 141, 82, 246, 56, 168, 163, 148, 103, 309, 245, 53,
159, 136, 67, 201, 262, 104, 312, 254, 80, 240, 38, 114, 1},
Quindi il periodo di 3 in base 340 è 30, ma dividendo 340 con 30, si
ha: 340=11.30+10, e quindi: 3340=311x30+10=(330)11.310,
Ma 3301(mod.341), e quindi anche (330)11111 =1(mod.341), inoltre,
essendo e 31056(mod.341), anche 3340=(330 )11.31056(mod.341).
Da ciò, 341 non è primo.
Quando si verifica che un numero n è del tipo:
• 2n-11(mod.n),
ed esiste un numero a, con a 2 per cui:
• an-1x(mod.n), x1;
Si dice che il numero è pseudo-primo in base 2.
118
Pseudo-primi
• Si ha, quindi, che 341 è pseudo-primo alla base 2.
• I numeri pseudo-primi sono rari, solo 1770 numeri
più piccoli di 25.109 sono pseudo-primi alle basi 2,
3, 5 e 7.
• L’Inverso del Teorema di Fermat serve per
escludere dal test di primalità tutti quei numeri che
non verificano la condizione dell’Inverso del
Teorema di Fermat, poiché essi non possono
essere in nessun caso primi.
119
Inverso del Teorema di Fermat
•
•
•
•
Lucas (1876)
Se ax-1:
È divisibile per n, per x coincidente con n-1
Non è divisibile per n, per x uguale ad una
parte aliquota di n-1,
• Allora, il numero n è primo.
120
Inverso del Teorema di Fermat
• Esempio:
• Sia a=3, n=65537=216+1;
• I divisori di n-1 sono: {1, 2, 22, 23, 24, 25, 26, 27, 28, 29, 210,
211, 212, 213, 214, 215, 216}.
• Se scrivo il resto delle divisioni tra le potenze di 3 con
esponenti le successive potenze di 2, ottengo la sequenza,
nella quale ciascun termine è il quadrato del precedente:
• {3, 9, 81, 6561, 54449, 61869, 19139, 15028, 282, 13987,
8224, 65529, 64, 4096, 65281, 65536, 1}.
• Dal fatto che 3 non ha il resto uguale a 1 prima dell’ultimo
termine della sequenza ed ha resto pari ad uno nell’ultimo
termine, si ha che n=65537=216+1 è un numero primo.
121
Test di Lucas
• Il Test di Lucas presenta l’inconveniente
che richiede la fattorizzazione del numero
n-1 ed una verifica per ciascuno dei fattori.
• La difficoltà è ridotta se il test è applicato ai
numeri della forma n=pk+1, con p primo.
• Tuttavia, se il numero da considerare è
grande, si richiedono noiosi calcoli.
122
Test di Lehmer
• Teorema 1. Se ax1(mod.N) per x=N-1, ma non per un
divisore proprio di N-1, allora N è primo.
• Questo metodo richiede:
• La completa fattorizzazione di N-1;
• Il numero dei valori di x può essere esageratamente
elevato;
• La condizione di primalità è sufficiente, ma non necessaria.
• Tali inconvenienti sono limitati, se N-1 è una potenza di 2.
123
Test di Lehmer
• Teorema 2. Se ax1(mod.N) per x=N-1, ma non
per x, tale che x è quoziente di N-1 sulla divisione
di alcuni suoi fattori primi, allora N è primo.
• Teorema 3. Se ax1(mod.N) per x=N-1 e se
axr>1, per x=(N-1)/p, e se r-1 è primo con N,
allora tutti i fattori primi di N sono della forma
npα-1, dove α è la più alta potenza al quale i primi
p occorrono come divisori di N-1.
124
Test di Lehmer
•
•
•
•
•
•
•
•
•
•
Esempio: sia N=9999999900000001,
Questo numero è dato da (1024-1)/(108-1).
Si ha, allora:
N-1 = [(1024-1)/(108-1)]-1 = 108(1016-1)/(108+1) = 108(108-1) = 28.58.32.11.73. 101.137.
I divisori di 28 e 58 (essendo 8 la potenza più elevata relativamente ai numeri primi)
sono stati scelti come valori di pα e per testare l’operazione seguente:
7(N-1)/107128121476353673=r(mod.N),
Allora r2=7(N-1)/5428233546143224(mod.N)
E, finalmente, r59999999900000000=N-1(mod.N) e r101(mod.N),
Essendo r2-1 primo con N, segue che ogni fattore di N è della forma: n28+1, ed anche
della forma: n58+1, o meglio della forma:
•
n108+1.
Ma N1/2<108, così N è primo, così si ha la completa fattorizzazione del numero 10 24+1 è:
• 1024+1=17.5882353.9999999900000001.
125
Test di Lehmer
• John Selfridge (1975) semplifica il Teorema
2, il quale permette di cambiare il valore di
a per qualche divisore di N-1.
• Egli stabilisce che se per qualche divisore
primo p di N-1, esiste un a tale che:
• a(N-1)/p≡r(mod.N), con r>1, ma a(N1)≡1(mod.N), allora N è primo.
126
Sequenza di Fibonacci
• Sequenza di Fibonacci (1282): 1, 2, 3, 5, 8, 13, …, (i-1)+i,
….
• Simon Stevin (1634), osserva tale sequenza e la collega al
problema circa il numero di conigli prodotti da una coppia
di conigli.
• Robert Simson nota che tale sequenza e nota che è data da:
(1+5)/2, radice dell’equazione quadratica X2-X-1=0.
• Tale successione ha suscitato interesse da parte di altri
matematici a partire dal 1750.
• Lucas (1876) a partire dall’equazione X2-X-1=0, stabilisce
le due sequenze definite da:
• Un=(an-bn)/(a-b) e Vn=an-bn=Un-1+Un+1.
127
Test di Lucas
• L’uso delle successioni:
• Un=(an-bn)/(a-b) e Vn=an-bn=Un-1+Un+1,
• È utile per provare se un numero di
Mersenne della forma 2m-1 sia primo, e
Lucas stesso stabilì che 2127-1 fosse primo.
• Con questo metodo fu trovato nel 1988 il
numero primo di Mersenne: 2110503-1.
128
Test di Lucas
• La “sequenza di Lucas” generalizza la sequenza all’equazione
quadratica al caso: x2-Px+Q=0, dove P e Q sono interi e
coprimi, tramite le formule:
• U2n=UnVn, V2n=(Vn)2-2Qn, U2n+1=Un+1Vn-Qn
e V2n+1=Vn+1Vn-PQn.
• Teorema (fondamentale) di Lucas. Se in una delle successioni
ricorsive Un determina che Up-1 è divisibile per p, ad esclusione
di ciascuno degli altri termini della serie, il cui rango è divisore
di p-1 iniziando così, il numero p è primo; proseguendo allo
stesso modo, se Up+1 è divisibile per p, ad esclusione di ciascuno
degli altri termini della serie il cui rango è un divisore di p+1
iniziato così, allora il numero p è primo.
129
Test di Lucas
• Teorema 2. Sia p=24q+3-1 nel caso in cui 4q+3 è
primo e 8q+7 è composto; noi produciamo la serie
rn: 3, 7 , 47, 2207, … dal significato della
relazione, per n>1,
• rn+1=rn2-2,
• Il numero p è primo, mentre il rango del primo
termine divisibile per p occupa un rango tra 2q+1
e 4q+2; il numero p è composto se alcuno dei
4q+2 primi termini della serie è divisibile per p.
130
Test di Pépin
• Dal teorema di Pépin si trova un algoritmo
per testare la primalità dei numeri di
Fermat.
• Un numero di Fermat della forma Fn=2k+1,
dove k=2n.
• Fermat asserì (erroneamente) che tutti i
numeri di tale forma fossero primi.
131
Scomposizione dei numeri di
Fermat Fn
• Goldbach (1729) provò che F5=232+1 sia
composto, dal fatto che F5=641.6700417.
• Verso la fine del 19° si cerca di trovare se F6 sia
primo o composto.
• Il più grande numero di Fermat esplorato col test
di Pépin è F22, che contiene 1262612 cifre, esso è
composto.
• Il più grande numero conosciuto essere composto
è F23471.
• Il primo numero di Fermat sconosciuto è F24.
132
Test di Pépin
• Teorema.
• La condizione necessaria e sufficiente
affinchè il numero an=2k+1, con k=2n sia
primo, per n>1, è: che il numero 5(an-1)/2+1
sia divisibile per an.
133