Cosa è “l’inverso (mod N)” di un numero

In questo articolo torniamo a parlare dei “numeri (mod N)”. (Se non li conoscete vi consiglio di leggere l’articolo del 15 maggio 2021). Il nostro interesse per l’argomento è legato al cifrario RSA (ma per i dettagli vi rimando ai prossimi articoli! Restate aggiornati xD).

Per prima cosa, consideriamo due numeri A e N coprimi. (Se non sapete cosa vuol dire “coprimi” leggete la parte iniziale di questo articolo). Ci chiediamo:

C’è un numero B tale che il resto della divisione (A x B)/N è 1?

Tutto poco chiaro? Facciamo un esempio.

Prendiamo come numeri 5 e 7. I due numeri sono coprimi perché il massimo comune divisore tra 5 e 7 è 1. A questo punto arriva la fatidica domanda:

C’è un numero B tale che il resto della divisione (5 x B)/7 è 1?

La risposta è SI, e il numero B che cerchiamo è 3. Infatti 3 x 5 = 15, e il resto della divisione 15/7 è 1.

Un modo sintetico per dire che “il resto della divisione (A x B)/N è 1” è il seguente: “B è “l’inverso (mod N)” di A”. Di seguito alcuni esempi:

Nel prossimo articolo scopriremo come calcolare velocemente l’inverso di un “numero (mod N)”. Nel frattempo scrivete pure nei commenti se avete dubbi o domande di qualunque tipo (ovviamente riguardanti la matematica xD) Buona crittografia!