TPSIT – Crittografia – Teorema d Eulero


Una conseguenza del piccolo teorema di Fermat è la seguente:

Sia m ed n positivi e p primo e m\;mod\;(p-1)=n\;mod\;(p-1) allora:

a^{m}\;mod\;p=a^{n}\;mod\;p

relazione molto utile per la cifratura a chiave asimmetrica RSA.

Il teorema di Fermat è generalizzato dal teorema di Eulero:

per ogni n ed ogni a che è coprimo (nessun divisore comune) di n vale la relazione

a^{\varphi (n)}\;mod\;n=1\;mod\;n

La funzione \varphi (n) è la funzione di Eulero che conta il numero di interi tra 1 ed n coprimi rispetto ad n.

Ad esempio:

\varphi (8)=4 infatti i numeri coprimi di 8 sono 1, 3, 5 e 7.

Ma come si calcola \varphi(p)?

Prima proposizione

Se p è un numero primo allora

\varphi (p^{k})=p^{k}-p^{k-1}

Seconda proposizione

se n=a\cdot b con a e b che non hanno alcun MCD se non l’1 allora

\varphi (a\cdot b)=\varphi(a)\varphi(b)

Corollario

se n=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot\cdot\cdot p_{k}^{k_{k}} con p_{1} e p_{k} numeri primi distinti allora:

\varphi(n)=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})\cdot\cdot\cdot (p_{r}^{k_{r}}-p_{r}^{k_{r}-1})

Questa voce è stata pubblicata in Senza categoria. Contrassegna il permalink.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *