La fattorizzazione dei grandi numeri interi:

Per un numero intero «non troppo grande», è abbastanza facile ottenerne la scomposizione in prodotto di fattori primi mediante divisioni successive per numeri primi (riconosciuti come divisori oppure, altrimenti, esaminati sistematicamente in ordine crescente). Per esempio, 45 = 5 × 9 = 5 × 3², oppure, in modo più sistematico, 4 851 = 3 ×1 617 = 3 × 3 ×539 = 3² × 7 ×77 = 3² × 7² × 11. Questo metodo raggiunge rapidamente i suoi limiti nel caso di un numero composto con fattori primi relativamente «grandi»: i criteri di divisibilità degli interi non aiutano più e il metodo della divisione sistematica per numeri primi crescenti allunga considerevolmente la procedura. Oggi, grazie ai computer e a metodi più raffinati, si possono fattorizzare numeri interi di un centinaio di cifre; ciononostante, non esistono ancora algoritmi di fattorizzazione abbastanza efficienti da fare molto meglio in tempi ragionevoli (il più grande intero, prodotto di due numeri primi, fattorizzato finora ha «soltanto» duecentocinquanta cifre).

Alle radici del problema -----------------------

Nel 17^º secolo si trovano già, nella corrispondenza tra Marin Mersenne e Pierre de Fermat, tracce di problemi di fattorizzazione di interi fino a dodici cifre: in un’epoca in cui non esistevano calcolatrici, è piuttosto notevole! Così, in una lettera del 1643 indirizzata da Fermat a Mersenne, ci si chiede se il numero 2 027 651 281 sia primo o composto e, in quest’ultimo caso, come si scomponga in fattori primi. Questa lettera ci fornisce inoltre preziosi indizi sullo stato dell’aritmetica dell’epoca e sulla sua evoluzione verso una moderna teoria dei numeri, di cui Fermat può essere considerato il fondatore.

Il metodo di fattorizzazione illustrato da Fermat si fonda essenzialmente sulla proprietà seguente: il prodotto di due numeri dispari può sempre essere scritto come differenza di due quadrati. Infatti, se p e q (con p > q) sono due numeri interi dispari, la loro somma e la loro differenza sono pari, il che permette di scrivere $pq={\left(\frac{p+q}{2}\right)}^2-{\left(\frac{p-q}{2}\right)}^2\mathrm{.}pq=\backslash left\; (\; \backslash frac\{p+q\}\{2\}\; \backslash right\; )^2-\; \backslash left\; (\; \backslash frac\{p-q\}\{2\}\; \backslash right\; )^2.$

Poiché R² – S² = (R – S)(R + S), ne segue che, se un intero dispari N è composto, esistono interi R e S tali che N = (R – S)(R + S). Questa proprietà può dunque condurre a un metodo generale di scomposizione: essendo dispari tutti i numeri primi (tranne 2), ogni intero composto è della forma 2*^k N (k* un numero naturale) con N dispari, che, se non è primo, potrà essere scritto come differenza di due quadrati e quindi fattorizzato. Se i fattori trovati sono primi, la scomposizione è completa; altrimenti si procede allo stesso modo con i fattori ancora scomponibili.

Ma, dato un intero dispari N, come determinare R e S tali che N = R² – S² ? L’idea è cercare R a partire dalla parte intera di $\sqrt{\mathrm{N}}\backslash sqrt\{\backslash rm\{N\}\}$, che indicheremo con c, per incrementi successivi: R = c + k, con k = 1, 2, 3… (R è necessariamente maggiore di $\sqrt{\mathrm{N}}\backslash sqrt\{\backslash rm\{N\}\}$ poiché N = R² – S²). Poiché N = R² – S² = (c + k)² – S², (c + k)² – N deve essere un quadrato (uguale a S²): questa è la condizione di arresto del ciclo di incremento. Trovato l’intero k, si ottiene anche R = (c + k), e lo stesso vale per S (che è la radice quadrata di (c + k)² – N): il problema è risolto!

Alcuni accorgimenti di calcolo permettono a Fermat di rendere il suo algoritmo meno laborioso di quanto sembri: la quantità da verificare, (c + k)² – N, viene calcolata per k = 1 osservando che, per un intero r, (c + 1)² – (c² + r) = (c² + 2c + 1) – (c² + r) = 2c + 1 – r, un’espressione molto più facile da calcolare «a mano» rispetto all’espressione iniziale quando c è «grande». Fermat usa poi il fatto che: (c + k + 1)² – N = (c + k)² – N + (2c + 1 + 2k) per passare da un valore di k al successivo.

Vediamo che cosa accade per il numero intero menzionato nella lettera: N = 2 027 651 281. Si comincia estraendo la radice quadrata di N, fermandosi alla sua parte intera; si trova c = 45 029 e un resto r = 40 440 (ossia, 2 027 651 281 = 45 029² + 40 440). Si calcola allora 2c + 1 – r, che è la quantità da verificare al passo k = 1; si trova 49 619. Questo numero non è un quadrato perché, dice Fermat, «nessun quadrato termina con 19» (vedi riquadro). Si passa dunque a k = 2, aggiungendo 2c + 1 + 2 = 90 061 a 49 619. Si ottiene 139 680, che non è ancora un quadrato. Per k = 3: 139 680 + 90 063 = 229 743 non è un quadrato. Per k = 4: 229 743 + 90 065 = 319 808 non è un quadrato… La lettera di Fermat ci informa che dovette proseguire fino a k = 12 (verificatelo!) per trovare 1 040 400, che è il quadrato di 1 020. Si ottengono così R = c + 12 = 45 041, S = 1 020, dunque N = (R – S)(R + S) = 44 021 × 46 061. La scomposizione si ferma qui, poiché 44 021 e 46 061 sono numeri primi (come si può verificare con il crivello di Eratostene; vedi il riquadro «Fermat, Mersenne e i numeri primi»).

a Beaumont-de-Lomagne, nel Tarn-et-Garonne.

Un metodo davvero efficace -----------------------------

Il metodo di Fermat permette dunque di fattorizzare efficacemente il numero N = 2 027 651 281: la procedura algoritmica converge in un numero relativamente ridotto di passi (12). Se si fossero cercati i fattori primi di N = 2 027 651 281 per la «via ordinaria», cioè mediante divisioni successive per numeri primi crescenti, sarebbe stato necessario, scrive Fermat, «dividere per tutti i numeri dal 7 fino a 44 021». Il suo algoritmo fa davvero molto meglio! Ma ciò dipende dal fatto che i due fattori primi p e q che compongono N sono «abbastanza vicini» tra loro. Il metodo proposto da Fermat parte da $c=\left[\sqrt{pq}\right]c=\backslash left\; [\backslash sqrt\{pq\}\backslash right\; ]$, cioè dalla parte intera della media geometrica dei due fattori, per avanzare verso R = (p + q) / 2, la loro media aritmetica. La differenza tra queste due medie dà quindi un’idea della lunghezza dell’algoritmo di Fermat; purtroppo, quanto più p e q si allontanano l’uno dall’altro, tanto più questa differenza cresce…

Questo metodo di fattorizzazione rimase tuttavia, fino agli anni Settanta, il più efficace per fattorizzare interi scelti opportunamente. Fu migliorato nel 1981 dall’americano Carl Pomerance (nato nel 1944), con un algoritmo chiamato crivello quadratico, nel quale si cercano R e S tali che N divida R² – S² (mentre nel metodo di Fermat R e S sono tali che N = R² – S²). Questo algoritmo rese possibile, nel 1994, grazie a diverse centinaia di computer e a mesi di lavoro, fattorizzare il numero RSA-129, un numero di centoventinove cifre prodotto di due grandi numeri primi.

Una sfida tra studiosi ---------------------

In un’altra lettera datata 1643, Fermat affrontò qualcosa di più impegnativo, con N = 100 895 598 169, in seguito alla richiesta formulata da Mersenne di «un metodo per scoprire nell’arco di un giorno se è primo o composto» (la corrispondenza tra gli studiosi dell’epoca aveva spesso il carattere di una sfida intellettuale…). Fermat spiegava raramente come otteneva i suoi risultati, e ciò impegnò molti matematici nel dimostrarli, fino al 20^º secolo! Fedele a questa abitudine, rispose, senza ulteriori spiegazioni, che il numero proposto dal suo corrispondente era composto da 898 423 e 112 303, che, aggiunse, erano primi.

Anche in questo caso Fermat avrebbe usato l’algoritmo precedente? Sicuramente no! Un’implementazione al computer di questo algoritmo mostra infatti che avrebbe dovuto arrivare fino a k = 187 723. Si vede quanto sia stringente la condizione di vicinanza dei due fattori: 898 423 e 112 303 sono troppo «lontani» l’uno dall’altro per poterli trovare in un tempo «ragionevole» con questo metodo. Allora, quale nuovo metodo avrà usato Fermat per raccogliere la sfida lanciata da Mersenne?

Fermat si interessò a particolari numeri, i numeri perfetti (uguali alla somma dei loro divisori propri, come 28, uguale a 1 + 2 + 4 + 7 + 14) e i numeri multiperfetti (interi per i quali un multiplo è uguale alla somma dei divisori propri, come 120, la cui somma dei divisori propri è 360, cioè 3 × 120). Tutti questi numeri furono studiati da Euclide, poi da Cartesio. Ora, un altro passo di questa seconda lettera rende evidente che Mersenne si interessa alla fattorizzazione di un numero N, supposto multiperfetto (questo numero fu probabilmente suggerito da Frénicle). La scomposizione di N in fattori primi è stabilita… o quasi, perché un certo fattore risulta più complicato degli altri da analizzare: si tratta precisamente di 100 895 598 169. Questo intero è primo? Basta chiederlo a Fermat!

Quest’ultimo affrontò il problema e lo trattò, quasi certamente, a partire da considerazioni sulle proprietà dei numeri multiperfetti. Il suo ragionamento avrebbe potuto essere il seguente: se N è k-perfetto, cioè se la somma σ (N) dei suoi divisori propri vale kN, con k «piccolo», allora i «grandi» fattori primi di σ (N) e di N sono gli stessi! Ora, 616 318 177 compare nella scomposizione di N; dunque il numero σ (616 318 177) compare in quella di σ (N), con σ (616 318 177) = 616 318 177 + 1. La scomposizione di 616 318 178 dà 2 × 73 × 898 423, con 898 423 primo; quest’ultimo numero è quindi anch’esso un fattore primo di N. Poiché non compare nella scomposizione iniziale, è un fattore di 100 895 598 169. Un’ultima divisione può condurre alla fattorizzazione cercata: 100 895 598 169 = 898 423 × 112 303. In modo meno laborioso, si può anche riutilizzare il ragionamento precedente per trovarla: σ (898 423) = 898 424 = 23 × 112 303; poiché 112 303 non compare neppure nella scomposizione iniziale di N, è anch’esso un fattore primo di 100 895 598 169. E il gioco è fatto!

La fattorizzazione resta difficile, per fortuna! ----------------------------------------------

Nel 17^º secolo, saper fattorizzare numeri interi molto grandi non aveva probabilmente altro interesse che dimostrare ai propri pari la propria ingegnosità nel calcolo. Oggi questa questione è diventata cruciale: un intero settore della sicurezza digitale si fonda sulla difficoltà di risolvere un simile problema di fattorizzazione! Sappiamo ormai generare numeri tanto difficili da fattorizzare che, anche dedicando a questo solo compito la potenza di tutti i nostri computer, non se ne verrebbe a capo in tempi ragionevoli. Lungi dall’essere un inconveniente, questa difficoltà è al centro stesso del sistema di crittografia oggi più usato: il sistema RSA, inventato nel 1977 da Ronald Linn Rivest (nato nel 1947), Adi Shamir (nato nel 1952) e Leonard Adleman (nato nel 1945), e diffuso come chiave di cifratura alla fine degli anni Novanta, con l’arrivo di Internet. Si tratta di un codice asimmetrico, con una chiave nota a tutti per cifrare i messaggi, detta chiave pubblica, e una chiave nota al solo destinatario per decifrarli, detta chiave privata. Il vantaggio di questo tipo di codice asimmetrico è che la chiave privata non transita su alcun canale di comunicazione.

Nel sistema crittografico RSA, la chiave pubblica è un numero N prodotto di due fattori primi p e q «molto grandi», che non è necessario conoscere per cifrare il messaggio (vedi riquadro), mentre la decodifica richiede non solo la conoscenza di N, ma anche quella dei due fattori p e q. Si comprende allora che, se N è «sufficientemente grande» e p e q sono scelti bene, considerati i limiti attuali delle tecniche di fattorizzazione, un tale sistema di cifratura è in pratica inattaccabile. Oggi si stima che scegliere un numero N di circa seicento cifre (p e q con circa trecento cifre ciascuno) ci metta al riparo da ogni minaccia per parecchie decine d’anni (al momento non si sa fare meglio che fattorizzare un numero di duecentocinquanta cifre).

Questo testo è tratto dalla conferenza tenuta da Daniel Perrin mercoledì 14 marzo 2018 alla Bibliothèque nationale de France, nell’ambito del ciclo «Un texte, un mathématicien».