Due esempi: fattorizzazione e MCD

I computer classici che esistono oggi sono incredibilmente veloci, e la loro velocità sembra essere in costante aumento. Per questo motivo, alcuni potrebbero essere portati a credere che i computer siano così rapidi che nessun problema computazionale sia al di là della loro portata.

Questa convinzione è falsa. Alcuni problemi computazionali sono talmente complessi per natura che, pur esistendo algoritmi per risolverli, nessun computer sulla Terra oggi è abbastanza veloce da eseguire questi algoritmi fino alla conclusione anche su input di dimensioni moderate nell'arco della vita di un essere umano — o persino nell'arco della vita della Terra stessa.

Per spiegare meglio, introduciamo il problema della fattorizzazione intera.

Fattorizzazione intera

Input: un intero $N\geq 2$
Output: la fattorizzazione in numeri primi di $N$

Per fattorizzazione in numeri primi di $N$ intendiamo una lista dei fattori primi di $N$ e delle potenze a cui devono essere elevati per ottenere $N$ tramite moltiplicazione. Ad esempio, i fattori primi di $12$ sono $2$ e $3,$ e per ottenere $12$ bisogna prendere il prodotto di $2$ alla potenza $2$ e $3$ alla potenza $1.$

$$12 = 2^2 \cdot 3$$

A meno dell'ordine dei fattori primi, esiste una sola fattorizzazione in numeri primi per ogni intero positivo $N\geq 2,$ un fatto noto come il teorema fondamentale dell'aritmetica.

Alcune semplici dimostrazioni di codice in Python saranno utili per spiegare ulteriormente la fattorizzazione intera e altri concetti correlati a questa discussione. Le seguenti importazioni sono necessarie per queste dimostrazioni.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

La funzione factorint del pacchetto di matematica simbolica SymPy per Python risolve il problema della fattorizzazione intera per qualsiasi input $N$ scegliamo. Ad esempio, possiamo ottenere la fattorizzazione in numeri primi di 12, che naturalmente coincide con la fattorizzazione sopra riportata.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Fattorizzare numeri piccoli come $12$ è facile, ma quando il numero $N$ da fattorizzare diventa più grande, il problema diventa più difficile. Ad esempio, eseguire factorint su un numero significativamente più grande causa un ritardo breve ma percettibile su un tipico computer personale.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

Per valori di $N$ ancora più grandi, le cose diventano impossibilmente difficili, almeno per quanto ne sappiamo. Ad esempio, la RSA Factoring Challenge, gestita da RSA Laboratories dal 1991 al 2007, offriva un premio in denaro di $100.000 per fattorizzare il seguente numero, che ha 309 cifre decimali (o 1024 bit in formato binario). Il premio per questo numero non è mai stato riscosso e i suoi fattori primi rimangono sconosciuti.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Non vale la pena eseguire factorint su RSA1024; non finirebbe nell'arco delle nostre vite.

L'algoritmo più veloce conosciuto per fattorizzare interi di grandi dimensioni è noto come il crivello del campo numerico. Come esempio dell'utilizzo di questo algoritmo, il numero RSA250 della sfida RSA, che ha 250 cifre decimali (o 829 bit in formato binario), è stato fattorizzato usando il crivello del campo numerico nel 2020. Il calcolo ha richiesto migliaia di anni-CPU-core, distribuiti su decine di migliaia di macchine in tutto il mondo. Qui possiamo apprezzare questo sforzo verificando la soluzione.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

La sicurezza del sistema crittografico a chiave pubblica RSA si basa sulla difficoltà computazionale della fattorizzazione intera, nel senso che un algoritmo efficiente per la fattorizzazione intera lo renderebbe vulnerabile.

Consideriamo ora un problema correlato ma molto diverso: il calcolo del massimo comune divisore (o MCD) di due interi.

Massimo comune divisore (MCD)

Input: interi non negativi $N$ e $M,$ di cui almeno uno positivo
Output: il massimo comune divisore di $N$ e $M$

Il massimo comune divisore di due numeri è il numero intero più grande che divide esattamente entrambi.

Questo problema è facile da risolvere con un computer — ha all'incirca lo stesso costo computazionale della moltiplicazione dei due numeri in input. La funzione gcd del modulo math di Python calcola il massimo comune divisore di numeri considerevolmente più grandi di RSA1024 in un batter d'occhio. (In effetti, RSA1024 è il MCD dei due numeri in questo esempio.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Ciò è possibile perché disponiamo di algoritmi molto efficienti per il calcolo del MCD, il più noto dei quali è l'algoritmo di Euclide, scoperto oltre 2.000 anni fa.

Potrebbe esistere un algoritmo veloce per la fattorizzazione intera che non abbiamo ancora scoperto, che permetterebbe di fattorizzare numeri grandi come RSA1024 in un batter d'occhio? La risposta è sì. Sebbene ci si potrebbe aspettare che un algoritmo efficiente per la fattorizzazione, semplice ed elegante come l'algoritmo di Euclide per il calcolo del MCD, sarebbe già stato scoperto, nulla esclude l'esistenza di un algoritmo classico molto veloce per la fattorizzazione intera, al di là del fatto che finora non siamo riusciti a trovarne uno. Potrebbe essere scoperto domani — ma non tratteneresti il respiro. Generazioni di matematici e informatici hanno cercato, e fattorizzare numeri come RSA1024 rimane al di là della nostra portata.