Crittografia/La matematica che devi conoscere: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Nessun oggetto della modifica |
||
Riga 37:
Per cifrari famosi, come ad esempio quello di Cesare, è molto utile ma non necessario, conoscere il Piccolo Teorema di Fermat
* <big> Piccolo teorema di Fermat </big>:
: Lemma 36:
:
:
:
L’enunciato di questo teorema compare in una lettera indirizzata da Fermat
ad un amico. Esso afferma che, se p è un numero primo, ed a è un intero
positivo qualunque, allora il numero
ap-a
è divisibile per p. In realtà vale un risultato più forte: se p non divide a, allora
a p-1 – 1
è divisibile per p.
La dimostrazione fu data nel 1736 da Eulero, che nel 1760 generalizzò il
teorema. Egli introdusse la funzione φ, detta totiente: per ogni intero positivo
n, indicò con φ(n) il numero di interi compresi fra 1 e n-1 che non hanno,
con n, divisori comuni non banali. Egli provò che, per qualsiasi intero
positivo a coprimo rispetto ad n il numero
a φ(n) - 1
è divisibile per n. Questo enunciato contiene il Piccolo Teorema di Fermat, in
quanto, per ogni numero primo p, si ha che φ(p)=p-1.
| |||