In questo articolo parleremo della cosiddetta “phi di Eulero”.
Partiamo con una definizione. Due numeri A e B si dicono “coprimi” (con l’accento sulla prima “i”) se il loro massimo comune divisore è uno. Ad esempio:
Siamo ora in grado di dare la definizione di “phi” di Eulero. xD
Se N è un numero, allora la “phi” di Eulero di N non è altro che la risposta alla seguente domanda:
QUANTI sono i numeri compresi tra 1 e N che sono coprimi con N?
Sembra una domanda con una risposta non scontata, e in effetti lo è! xD Per rispondere, proviamo ad esaminare casi diversi e con un livello crescente di difficoltà.
Caso 1. Se P è un numero primo, QUANTI sono i numeri compresi tra 1 e P che sono coprimi con P?
Risposta. Ci sono (P – 1) numeri compresi tra 1 e P che sono coprimi con P.
Spiegazione. Ricordiamo che un numero si dice “primo” quando i suoi unici divisori sono 1 e il numero stesso. Per questo motivo:
Esempio. Siccome 7 è un numero primo, ci sono 6 numeri compresi tra 1 e 7 che sono coprimi con 7. (Questi numeri sono: 1, 2, 3, 4, 5 e 6)
Il caso 1 era (relativamente) facile, per cui adesso ci complicheremo un poco la vita! xD
Caso 2. Se P e Q sono due numeri primi, QUANTI sono i numeri compresi tra 1 e (P x Q) che sono coprimi con (P x Q)?
Risposta. Ci sono (P – 1) x (Q – 1) numeri compresi tra 1 e (P x Q) che sono coprimi con (P x Q).
Spiegazione. Questo caso è più complicato del precedente. Usando l’intuito, però, ci accorgiamo che:
Esempio. Siccome 3 e 5 sono due numeri primi e 3 x 5 = 15, la “phi” di Eulero di 15 è (3 – 1) x (5 – 1) = 2 x 4 = 8
Il caso 2 è importantissimo per chi studia crittografia. (Il perché lo scopriremo quando parleremo del cifrario RSA!)
Caso 3. Se N è un numero NON primo, quanti sono i numeri compresi tra 1 e N che sono coprimi con N?
Rispondere a questa domanda può essere facile oppure difficile (anche per un computer).
Sotto-caso FACILE. Se si conosce la fattorizzazione di N (che è come dire “si conoscono i numeri primi che moltiplicati tra loro danno come risultato N”), allora calcolare la “phi” di Eulero di N diventa un problema molto facile. (Oggi non parleremo nel dettaglio di questo argomento per non mettere troppa carne sul fuoco. Sappiate però che per quanto riguarda l’RSA questo sotto-caso non ha molta importanza. Ad avere importanza per l’RSA sono invece il “caso 2” e il prossimo “sotto-caso DIFFICILE ANCHE PER UN COMPUTER”).
Sotto-caso DIFFICILE ANCHE PER UN COMPUTER. Calcolare la “phi” di Eulero di N diventa una Mission Impossible quando NON si conosce la fattorizzazione di N. Mi spiego meglio:
Quanto vale la “phi” di Eulero di 2231? (Suggerimento: 2231 è il prodotto di due numeri primi)
Chiamiamo P e Q i due numeri primi (sconosciuti!) che moltiplicati tra loro danno come risultato 2231. In altre parole:
2231 = (P x Q)
Per quanto detto quando abbiamo parlato “caso 2”, la “phi” di Eulero di (P x Q) (e quindi di 2231) è 2231 – P – Q + 1
A questo punto dobbiamo alzare bandiera bianca. Dato che non conosciamo i valori di P e di Q, non sappiamo neanche quanto vale (2231 – P – Q + 1). Che fregatura! 🙁
Al momento i matematici non conoscono un modo per calcolare la “phi” di Eulero di un numero senza conoscere la sua fattorizzazione. Questo fatto, a prima vista spiacevole, è in realtà una gran fortuna! La sicurezza del cifrario RSA, infatti, non è legata solamente al problema della fattorizzazione (ne abbiamo parlato nell’articolo del 29 marzo 2021), ma anche al problema di come calcolare la “phi” di Eulero di un numero senza conoscere i suoi fattori primi. (Per i dettagli della questione vi rimando agli articoli futuri riguardanti l’RSA e la “phi” di Eulero xD).
Il nostro articolo sulla “phi” di Eulero termina qui. Se avete dubbi o domande a riguardo scrivete pure nei commenti. Buona crittografia! xD
Apri un sito e guadagna con Altervista - Disclaimer - Segnala abuso - Privacy Policy - Personalizza tracciamento pubblicitario