Dato un numero N prodotto di due numeri primi (a*b=N) esiste una regola, al di fuori della scomposizione in fattori primi per individuare a e b? Se immaginiamo, infatti, N abbastanza grande (es. un numero composto da 100 cifre i tentativi della scomposizione per trovare a e b non possono essere fatti nemmeno da un computer!!! Perchè gli antichi matematici si interessarono del rapporto aureo e dove trovo del materiale in immagini che riguardi questo argomento?

Sarei particolarmente
felice di poter annunciare al lettore ed alla comunità
un metodo, algoritmo o regola per scomporre un prodotto
di primi dell’ordine di 200 cifre: diverrei ricco e
famoso in un sol colpo.

Quella che il lettore
pone è, direi, una delle più grandi sfide del secolo
perché l’uomo che riuscirà a trovare quel metodo
avrà, contemporaneamente, distrutto il punto cardine del
miglior algoritmo di crittografia mai concepito da mente
umana: l’RSA (si veda a tale proposito un articolo
già apparso su Eureka).

E la trama sarebbe pure
buona per un gran bel libro giallo, si immagini uno
scienziato, da solo nella sua stanza al dipartimento di
matematica che verifica e riverifica un metodo
rivoluzionario di scomposizione in numeri primi.
All’inizio nessuno si rende conto della portata
della sua scoperta, che tutti i codici potrebbero venire
violati: dai conti in banca agli armamenti. Ma, poi,
qualcuno viene a sapere della scoperta e, da quel giorno,
la vita di quello scienziato non sarà più la stessa

Divagazioni a parte, il
problema della fattorizzazione è considerato, ad oggi, computazionalmente
intrattabile
, ovvero di complessità (intesa come
quantità di tempo e spazio impiegata per
l’elaborazione) tale da non poter essere risolto
“per forza bruta” da alcun calcolatore.

Scomporre in fattori
primi un numero vuol dire verificarne la divisibilità
per ciascun numero della serie dei numeri primi che lo
precedono. Il Teorema dei Numeri primi asserisce che il
numero dei numeri primi minori o uguali n è circa
n/log n. Ciò implica che dovremmo eseguire circa
1058 divisioni per scomporre un numero di 200
cifre.

Supponendo di avere un
supercomputer in grado di eseguire un miliardo di
divisioni al secondo impiegando numeri a 60 cifre (roba
da fantascienza, almeno ad oggi), impiegheremmo 1041
(miliardi di miliardi di miliardi di miliardi) anni.

Per un approfondimento
su questi temi, si consulti l’elenco di risposte
nella sezione Matematica di ScuolaItalia.

 


Per il Rapporto Aureo ed
i Numeri di Fibonacci si veda
una risposta precedente.

Per un po’ di
storia sul rapporto aureo il sito:

http://www.geom.umn.edu/~demo5337/s97b/art.htm