Piccolo Teorema di Fermat: dimostrazione

Video 3 del percorso: "Crittografia".
In questa lezione presenteremo, seppur in forma semplificata, alcuni risultati della struttura matematica su cui si fonda il nocciolo dell'algoritmo RSA: l'Aritmetica Modulare.

Notiamo che nell'algoritmo assumono importanza fondamentale i resti delle divisioni intere modulo N delle potenze eseguite: infatti sono esattamente questi resti che costituiscono il crittogramma prima, e il messaggio originale in fondo alla procedura. Per questo definiamo un’aritmetica basata sui rapporti tra tali resti, detti classi di resto.
L'ultimo risultato presentato, il Piccolo Teorema di Fermat rappresenta il pilastro su cui si basa il funzionamento di RSA, ma è anche un risultato centrale nella teoria dei numeri primi.
Come tutto il video, può quindi essere apprezzato anche da chi non è interessato alla crittografia.

Prerequisiti: un’introduzione, anche breve, al concetto di aritmetica modulare.