L'Inverso Moltiplicativo e l'Algoritmo di Euclide: Come "Dividere" in Crittografia

-

Bentornati su izytech.dev! Nel precedente articolo abbiamo esplorato il cuore pulsante della crittografia: l'aritmetica modulare. Abbiamo visto come i computer utilizzino la matematica dei "resti" per mantenere i numeri piccoli e i calcoli ultra-veloci. Tuttavia, avevamo concluso la lezione con un grosso ostacolo: in questo mondo circolare, la divisione non esiste.

Se non possiamo dividere un numero per decifrare un messaggio, come facciamo a tornare indietro? La risposta risiede in uno dei concetti più affascinanti della teoria dei numeri: l'Inverso Moltiplicativo e un algoritmo vecchio di millenni che ci permette di calcolarlo.

L'Illusione della Divisione

Pensate alla matematica tradizionale. Dividere un numero per 5 è esattamente la stessa cosa che moltiplicarlo per 1/5 (il suo reciproco). In crittografia, usiamo la stessa identica logica, ma poiché non possiamo usare i numeri decimali o le frazioni, dobbiamo trovare un numero intero che si comporti esattamente come quel reciproco.

Questo numero speciale si chiama inverso moltiplicativo (spesso indicato con un esponente -1, ad esempio x-1). Per definizione, l'inverso moltiplicativo di un numero è quel valore che, moltiplicato per il numero originale all'interno di un modulo specifico, dà come risultato l'identità moltiplicativa, ovvero 1.

C'è solo un problema: non tutti i numeri possiedono un inverso moltiplicativo!

La Regola d'Oro: Essere "Coprimi"

Affinché un numero abbia un inverso in un determinato mondo modulare, deve rispettare una condizione ferrea: il numero e il modulo devono essere primi tra loro (o coprimi). Questo significa che non devono condividere nessun fattore primo. In termini matematici, il loro Massimo Comune Divisore (MCD) deve essere esattamente uguale a 1.

Se l'MCD è diverso da 1, l'inverso moltiplicativo semplicemente non esiste e l'operazione fallisce. In crittografia, sapere rapidamente se due numeri colossali (lunghi centinaia di cifre) sono coprimi è una questione di vita o di morte per l'algoritmo.

L'Algoritmo di Euclide: Un'Eredità Millenaria

Per scoprire se due numeri sono coprimi, abbiamo bisogno di trovare il loro MCD. Fortunatamente, uno degli algoritmi più efficienti per farlo è anche uno dei più antichi mai scoperti dall'umanità: l'Algoritmo di Euclide.

Invece di scomporre numeri immensi in fattori primi (un processo che richiederebbe millenni ai computer moderni), l'algoritmo di Euclide utilizza un principio geniale e velocissimo basato sui resti:

  • Prendi due numeri, x e y.
  • Il Massimo Comune Divisore tra x e y è esattamente identico al Massimo Comune Divisore tra y e il resto della divisione di x per y (chiamiamolo r).
  • In formule: MCD(x, y) = MCD(y, r).

Sostituendo ripetutamente il numero più grande con il resto, il problema diventa sempre più piccolo a una velocità sbalorditiva, finché il resto non diventa zero. L'ultimo resto non nullo che otteniamo è il nostro MCD!

Perché è così importante?

È straordinario pensare che i protocolli di sicurezza che oggi proteggono le nostre carte di credito e le nostre e-mail su internet affondino le loro radici in calcoli concepiti nell'antica Grecia. Gli antichi matematici non avevano i computer, quindi erano costretti a inventare metodi estremamente intelligenti per calcolare le cose a mano. Questa stessa efficienza manuale è ciò che rende i loro algoritmi perfetti per essere programmati sulle macchine di oggi.

Ricapitolando: oggi abbiamo scoperto che per "dividere" dobbiamo usare gli inversi moltiplicativi, che questi esistono solo se l'MCD è 1, e che l'Algoritmo di Euclide ci permette di verificare questa condizione in frazioni di secondo. Nella prossima lezione, faremo l'ultimo passo: modificheremo questo antico algoritmo (nell'Algoritmo di Euclide Esteso) per non limitarci a scoprire se l'inverso esiste, ma per calcolarlo materialmente. Restate sintonizzati!

Riferimenti Bibliografici e Materiale di Studio

  • Coursera: Mathematical Foundations of Cryptography (Lezione 3: Inversi Moltiplicativi e Algoritmo di Euclide).
  • Daniele Venturi (2012). Crittografia nel Paese delle Meraviglie. Springer. (Capitoli introduttivi sull'algebra modulare).
  • Carlo Casolo. Appunti di Teoria Elementare dei Numeri. Università degli Studi di Firenze. (Per le dimostrazioni complete sull'algoritmo euclideo).

Comments

Post a Comment

Popular posts from this blog

How to Install Ubuntu 24.04 WSL on Windows 10 and 11

-
Introduction This guide shows you step-by-step how to install Ubuntu 24.04 LTS using WSL (Windows Subsystem for Linux) on Windows 10 or Windows 11. It's a great solution to run Linux without dual boot or virtual machines. Requirements Windows 10 (version 2004 or later) or Windows 11 Internet connection Administrator access 1. Enable WSL Open PowerShell as administrator and run this command: wsl --install This command enables the necessary features, installs the WSL platform, and downloads Ubuntu (usually the latest stable version). 2. Install Ubuntu 24.04 Manually (if needed) If you want to install Ubuntu 24.04 specifically, you can do it manually: wsl --install -d Ubuntu-24.04 Or if WSL is already installed: wsl --list --online wsl --install -d Ubuntu-24.04 3. First Launch and Setup After installation, open Ubuntu from the Start Menu. The first time you launch it, y...
Read more

Introduction to Rust: Writing Your First "Hello, World!"

-
Getting Started with Rust: A Beginner’s Guide Getting Started with Rust: A Beginner’s Guide Published on July 20, 2025 Setting Up the Workspace First, we need to establish a directory to store our code. While Rust is indifferent to its location, it is good practice to keep your projects well-organized. Open a terminal (or command prompt) and create a directory for your project. For Linux, macOS, and PowerShell (on Windows): # Create a "projects" directory in your home directory mkdir ~/projects # Enter the newly created directory cd ~/projects # Create the directory for our specific project mkdir hello_world # Enter the project directory cd hello_world For the Windows Command Prompt (CMD): > mkdir "%USERPROFILE%\projects" > cd /d "%USERPROFILE%\projects" > mkdir hello_world > cd hello_world Writing and Executing the P...
Read more

Getting Started with Cargo in Rust: A Beginner-Friendly Guide

-
Getting Started with Cargo in Rust: A Beginner-Friendly Guide Cargo is the default build tool and package manager for Rust. It helps you build your code, download libraries (called dependencies ), and keep everything organized. 1. What Is Cargo? When you use Cargo, you don’t have to compile your code manually with rustc . Cargo makes everything easier, especially for bigger projects. You can: Build your code Add external libraries (dependencies) Run your program Check for compile-time errors 2. Check if Cargo is Installed If you installed Rust using the official method ( rustup ), Cargo is already installed. To check, run this command in your terminal: $ cargo --version If you see a version number, you're ready! 3. Create a New Project Now, let’s create a new Rust project using Cargo: $ cargo new hello_cargo $ cd hello_cargo This creates a folder named hello_cargo with two important things inside: Car...
Read more