Tempo fa mi è capitato di imbattermi sui numeri primi , e penso che abbiano colpito un po' chiunque per la loro proprietà .
Ok! Questo è un nuovo tema!
Ma perchè lo hai catalogato come
pseudo scienza?
Tu stai proponendo un problema matematico aperto e interessante. In quanto problema matematico è decisamente un problema scientifico.
Mi permetto quindi di suggerire agli amministratori uno spostamento della discussione, almeno dentro la categoria
altre scienzeComunque, veniamo alla domanda ed al metodo proposto per tentare una soluzione.
La domanda è: dato un numero arbitrario,
n, esiste un metodo generale che consenta di asserire che si tratti di un numero primo?
Per rispondere, occorre trovare un algoritmo che consenta di dirci se quel numero è un numero primo.
Un test che potrebbe sembrare immediato consiste nel metodo classico. Cioè provare a dividere in numero
n per tutti i numeri primi,
p, tali che
p<
n.
E' ovvio che un tale metodo funzioni. Ma la domanda cruciale è: questo metodo è praticabile?
Se il numero che vogliamo testare è sufficientemente piccolo, non ci sono difficoltà, come tutti avete appreso sin dalle scuole elemntari.
Ma se il numero è grande, l'operazione può implicare un numero elevatissimo di divisioni e quindi un tempo di calcolo non sostenibile.
Uno potrebbe pensare: non c'è problema! Faccio fare il calcolo ad un computer! Il che significa che devo produrre un codice che faccia per me le divisioni. Ma scrivere questo codice, significa che io devo dire al computer quali divisioni deve fare. Cioè gli devo dire per quali numeri deve provare a dividere il mio numero
n.
In linea di principio ho, apparentemente, due possibilità.
La prima è quella di fornire al computer una tabella con tutti i numeri primi minori di
n. Vedete subito che questa è una cosa impossibile. Il programma deve avere validità generale. Cioè deve funzionare per qualsiasi valore di
n. E siccome i numeri primi sono infiniti, ed
n può quindi essere arbitrariamente grande allora dovrei fornire una tabella infinita.
A parte le dimensioni illimitate della tabella, questa soluzione è una falsa soluzione. Perchè la disponibilità della tabella fornirebbe immediatamente la soluzione senza alcun calcolo. Se la tabella contiene tutti i numeri primi, allora la tabella deve contenere anche in numero
n, se questo fosse un numero primo!
In pratica, la costruzione di questa tabella implica che ci sia una procedura per costruire tutta la sequenza dei numeri primi.
Ed ecco quale potrebbe essere il secondo approccio alla soluzione del nostro problema originale.
Dato il numero
n il computer deve calcolare solo una tabella parziale dei numeri primi. Cioè è sufficiente che calcoli solo i numeri primi
p che siano minori o uguali ad
n. E la soluzione verrebbe fornita immediatamente. Se il nostro programma genera in numero
n, allora questo è un numero primo. Se non lo genera, allora
n non è un numero primo.
Ed ecco il vero problema. Esiste la maniera che mi consenta di scrivere questa tabella dei numeri primi minori di
n per
n arbitrariamente grande?
Sicuramente, esistono formule semplici che generano numeri primi arbitrariamente grandi. Ma queste formule non generano tutti i numeri primi. Purtroppo, generano solo i numeri primi che, oltre ad essere primi, godono dell'ulteriore proprietà di essere generati da quella formula. E questi non sono tutti i numeri primi!
Allora posso scrivere un algoritmo che, dato un numer primo
p, sia capace di calcolare il numero primo successivo nella sequenza? Oppure, posso scrivere un algoritmo che, dato un numero
n arbitrariamente grande, sia capace di fattorizzarlo in numeri primi?
I due problemi hanno complessità equivalente. In entrambi i casi, il numero di operazioni da fare cresce esponenzialmente con
n!
Il problema, pur disponendo dell'algoritmo idoneo, diviene presto praticamente insolubile. Non importa quanto veloce sia il mio ipotetico computer. Comunque sia, dato che i numeri primi sono infiniti, il numero di operazioni da fare diviene presto così elevato che, anche alla più alta velocità di calcolo immaginabile, il tempo di calcolo necessario diviene presto superiore al tempo di vita dell'Universo.
Un problema con questo tipo di complessità, si dice che appartiene alla
classe di complessità P.
Il che vuol dire che non può essere risolto in un tempo finito. Anche se esiste un algoritmo che potrebbe produrre una soluzione in un tempo finito, se implementato su un
computer quantistico.
Comunque, al momento nessuno sa veramente se sia possibile (o se abbia veramente senso) realizzare un computer quantistico. Quindi l'algoritmo di cui parlo è puramente ipotetico.
Metodi come quello di fido, in verità non producono nulla di significativo. Se guardate bene ciò che fanno, sostanzialmente producono una distribuzione arbitraria di numeri. Ad esempio, lui ci mostra che il numero 523 è un numero primo e rispecchia la proprietà che lui si è inventato. Peccato che fido non prenda in considerazione i numeri 325 e 352 ch godono della stessa proprietà del numero 523 pur non essendo primi. Comunque la si metta, il metodo di fido produce numeri, a siccome anche i numeri primi sono numeri, produce anche alcuni di essi. In pratica, quel metodo non serve a nulla.
Fido ha proposto un problema interessante, ma ha tentato un tipo di soluzione eccessivamente ingenua.
Il calcolo di un numero primo arbitrariamente grande è un'operazione difficilissima da portare a compimento.
Chi ci riuscisse, avrebbe decriptato tutti i codici di sicurezza sin qui esistenti. La chiave dei codici, inclusi quelli delle vostre carte di credito, consite in un numero che, in genere, è dato dal prodotto di due numeri primi molto grandi. Se uno sapesse come fare la scomposizione in fattori in tempi accessibili, allora ogni codice di sicurezza crollerebbe.
Gli informatici, dovrebbero riuscire a sviluppare questo tema meglio di quanto possa farlo io!
Al momento, per dare a tutti un'idea pratica del livello di complessità del problema sollevato da fido, mi limito ad indicarvi il link alla EFF Cooperative Computing Awards, che ha messo in palio dei premi in danaro per chi riuscirà a raggiungere certi traguardi.
https://www.eff.org/awards/coopVedete che alcuni premi sono stati assegnati e la data di assegnazione è riportata. Ma vedete anche che alcuni premi sono ancora in attesa, nonostante l'ammontare di danaro messo in palio non sia certo esiguo!
Se volete, provateci e...buona fortuna!