Două exemple: factorizarea și CMMDC

Calculatoarele clasice existente astăzi sunt incredibil de rapide, iar viteza lor pare să crească neîncetat. Din acest motiv, unii ar putea fi tentați să creadă că procesoarele sunt atât de rapide încât nicio problemă computațională nu le depășește capacitățile.

Această credință este falsă. Unele probleme computaționale sunt atât de complexe prin natura lor încât, deși există algoritmi pentru a le rezolva, niciun calculator de pe planeta Pământ nu este astăzi suficient de rapid pentru a rula acești algoritmi până la capăt, chiar și pentru intrări de dimensiuni moderate, în decursul vieții unui om — sau chiar în decursul existenței Pământului însuși.

Pentru a explica mai bine, haideți să introducem problema factorizării întregi.

Factorizarea întreagă

Intrare: un număr întreg $N\geq 2$
Ieșire: descompunerea în factori primi a lui $N$

Prin descompunerea în factori primi a lui $N$ înțelegem o listă a factorilor primi ai lui $N$ și puterile la care trebuie ridicați pentru a obține $N$ prin înmulțire. De exemplu, factorii primi ai lui $12$ sunt $2$ și $3,$ iar pentru a obține $12$ trebuie să luăm produsul lui $2$ la puterea $2$ și al lui $3$ la puterea $1.$

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

Până la ordinea factorilor primi, există o singură descompunere în factori primi pentru fiecare număr întreg pozitiv $N\geq 2,$ fapt cunoscut sub numele de teorema fundamentală a aritmeticii.

Câteva demonstrații simple de cod în Python vor fi utile pentru a explica în continuare factorizarea întreagă și alte concepte legate de această discuție. Importurile de mai jos sunt necesare pentru aceste demonstrații.

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

import math
from sympy.ntheory import factorint

Funcția factorint din pachetul de matematică simbolică SymPy pentru Python rezolvă problema factorizării întregi pentru orice intrare $N$ alegem. De exemplu, putem obține descompunerea în factori primi pentru 12, care corespunde în mod natural factorizării de mai sus.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Factorizarea numerelor mici precum $12$ este ușoară, dar pe măsură ce numărul $N$ de factorizat devine mai mare, problema devine mai dificilă. De exemplu, rularea factorint pe un număr considerabil mai mare provoacă o întârziere scurtă, dar vizibilă, pe un calculator personal obișnuit.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

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

Pentru valori și mai mari ale lui $N,$ lucrurile devin imposibil de dificile, cel puțin după câte știm. De exemplu, RSA Factoring Challenge, organizat de RSA Laboratories din 1991 până în 2007, oferea un premiu în bani de 100.000 de dolari pentru factorizarea numărului de mai jos, care are 309 cifre zecimale (sau 1024 de biți în reprezentare binară). Premiul pentru acest număr nu a fost niciodată revendicat, iar factorii săi primi rămân necunoscuți.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Nu are rost să rulăm factorint pe RSA1024 — nu ar termina în decursul vieților noastre.

Cel mai rapid algoritm cunoscut pentru factorizarea numerelor întregi mari este cunoscut sub numele de ciurul corpului de numere. Ca exemplu al utilizării acestui algoritm, numărul RSA250 din provocarea RSA, care are 250 de cifre zecimale (sau 829 de biți în reprezentare binară), a fost factorizat folosind ciurul corpului de numere în 2020. Calculul a necesitat mii de ani-core CPU, distribuit pe zeci de mii de mașini din întreaga lume. Putem aprecia acest efort verificând soluția.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

Securitatea criptosistemului cu cheie publică RSA se bazează pe dificultatea computațională a factorizării întregi, în sensul că un algoritm eficient pentru factorizarea întreagă l-ar compromite.

Acum să considerăm o problemă înrudită, dar foarte diferită: calculul celui mai mare divizor comun (sau CMMDC) a două numere întregi.

Cel mai mare divizor comun (CMMDC)

Intrare: numere întregi nenegative $N$ și $M,$ cel puțin unul dintre ele pozitiv
Ieșire: cel mai mare divizor comun al lui $N$ și $M$

Cel mai mare divizor comun a două numere este cel mai mare număr întreg care divide exact ambele numere.

Această problemă este ușor de rezolvat cu un calculator — are aproximativ același cost computațional ca înmulțirea celor două numere de intrare. Funcția gcd din modulul Python math calculează cel mai mare divizor comun al unor numere considerabil mai mari decât RSA1024 într-o clipă. (De fapt, RSA1024 este CMMDC-ul celor două numere din acest exemplu.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Acest lucru este posibil deoarece avem algoritmi foarte eficienți pentru calculul CMMDC, cel mai cunoscut dintre care este algoritmul lui Euclid, descoperit în urmă cu peste 2.000 de ani.

Ar putea exista un algoritm rapid pentru factorizarea întreagă pe care pur și simplu nu l-am descoperit încă, permițând factorizarea în clipa ochiului a unor numere mari precum RSA1024? Răspunsul este da. Deși ne-am putea aștepta ca un algoritm eficient pentru factorizare, la fel de simplu și elegant ca algoritmul lui Euclid pentru calculul CMMDC, să fi fost descoperit până acum, nimic nu exclude existența unui algoritm clasic foarte rapid pentru factorizarea întreagă, în afară de faptul că nu am reușit să găsim unul până în prezent. Ar putea fi descoperit mâine — dar nu-ți ține respirația. Generații de matematicieni și informaticieni au căutat, iar factorizarea unor numere precum RSA1024 rămâne în afara posibilităților noastre.