Come calcolare una “potenza (mod N)”

Nell’articolo del 13 maggio 2021 abbiamo parlato per la prima volta dei “numeri (mod N)”. Oggi scopriremo invece come calcolare un “elevamento a potenza (mod N)”.

Riprendiamo quindi la definizione di “numero (mod N)”. Se A e B sono due numeri, allora “A (mod N)” è semplicemente il resto della divisione A/N. Ad esempio:

• 5 (mod 2) = 1
• 15 (mod 6) = 3

Fin qui tutto (abbastanza) facile, ma alziamo l’asticella:

Supponiamo che un ragazzo di nome Bob voglia scoprire quanto fa “3⁷⁵ (mod 7)”. (Perché Bob è così masochista? La risposta alla fine di questo articolo xD). Sicuramente Bob NON può calcolare 3⁷⁵, perché le calcolatrici “standard” (tipo quelle scientifiche che si usano nelle scuole superiori) non permettono di calcolare numeri così grandi. Bob deve quindi trovare un altro modo per ottenere il risultato che cerca. Ecco come procede:

1. Bob scrive 75 (l’esponente di 3⁷⁵) come somma di potenze distinte di 2 (se non conoscete l’argomento leggete l’articolo del 14 maggio). Il risultato è 75 = 1 + 2 + 8 + 64
2. Bob scrive 3⁷⁵ nel seguente modo: 3⁷⁵ = 3^{1 + 2 + 8 + 64} = 3¹ x 3² x 3⁸ x 3⁶⁴
3. Bob calcola 3¹ (mod 7) = 3
4. Bob calcola 3² (mod 7) = 9 (mod 7) = 2
5. Bob calcola 3⁴ (mod 7) = (3²)² (mod 7) = 2² (mod 7) = 4
6. Bob calcola 3⁸ (mod 7) = (3⁴)² (mod 7) = 4² (mod 7) = 16 (mod 7) = 2
7. Bob calcola 3¹⁶ (mod 7) = (3⁸)² (mod 7) = 2² (mod 7) = 4
8. Bob calcola 3³² (mod 7) = (3¹⁶)² (mod 7) = 4² (mod 7) = 16 (mod 7) = 2
9. Bob calcola 3⁶⁴ (mod 7) = (3³²)² (mod 7) = 2² (mod 7) = 4
10. Bob calcola 3⁷⁵ (mod 7) = 3¹ x 3² x 3⁸ x 3⁶⁴ (mod 7) = 3 x 2 x 2 x 4 (mod 7) = 48 (mod 7) = 6

Come potete notare, Bob è riuscito a calcolare 3⁷⁵ (mod 7) in poco tempo! (Lo stesso procedimento usato da Bob risulta ovviamente funzionante e veloce anche per le altre “potenze (mod N)”, altrimenti non ne avremmo parlato in questo articolo! xD)

Rimane però un dilemma da scogliere, e in realtà è il più importante di tutti xD (se avete altri dubbi scrivete pure nei commenti):

Perché Bob è così masochista da voler sapere quanto fa 3⁷⁵ (mod 7)? Non sappiamo se Bob abbia oppure no problemi riguardanti il dolore, però sappiamo che il calcolo delle “potenze (mod N)” è molto utilizzato in crittografia. Per dirne una, il cifrario RSA utilizza il calcolo delle “potenze (mod N)” sia per cifrare che per decifrare i messaggi. (Ancora qualche articolo e riusciremo finalmente a spiegare come funziona l’ RSA! Manca veramente poco!)

Il nostro articolo termina qui. Per qualunque domanda o dubbio non esitate a scrivere nei commenti. Buona crittografia! xD