Ricerca Numeri primi metodo dimensione

[claugoru]

Buon giorno
Mi chiamo Claudio Govi e vorrei postare una mia teoria sulla ricerca dei numeri primi.
Questa teoria si basa sulla ricerca di questi numeri dentro una dimensione finita e non su un numero solo. Non sono un matematico, sono un programmatore, e spero mi scuserete se il mio linguaggio non sraò molto matematico

Per dimensione finita intendo la distanza che c’è tra un due numeri dispari consecutivi elevati al quadrato. Questa distanza la si può calcolare sulla base di 8 perché la distanza minima tra due numeri dispari consecutivi è (3^2-1^2= 8) e si incrementa di 8 in 8, per cui ogni numero di (8^n) rappresenta la distanza tra due numeri dispari consecutivi.

Diciamo che la mia dimensione di X sia uguale a 200 ((200+4)/4)=51 perciò avrò (51^2 - 49^2).
In questa dimensione di 200 e cioè da 2401 a 2601 ci saranno racchiusi tutti i divisori primi da 2 a 51 e cioè 2-3-5-7-11-13-17-19-23-29-31-37-41-43-47

Eliminando da questa dimensione tutti i numeri pari e i due numeri al quadrato 2401 e 2601, otterremo 99 numeri dispari tra cui ci saranno i potenziali numeri primi che noi dovremo individuare, e i nostri divisori diventeranno 3-5-7-11-13-17-19-23-29-31-37-41-43-47.

Per scoprire quali numeri dispari di questi 99 sono primi dovrò interrogare tutti i 14 divisori primi e se nessuno di questi dividerà il numero preso in esame questo sarà un numero primo.

Facciamo un esempio…

2401+2=2403 divisore 3
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+4=2405 divisore 5 - 13 - 37
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+6=2407 divisore 29
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+8=2409 divisore 3 - 11
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+10=2411 divisore nessuno
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+12=2413 divisore 19
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+14=2415 divisore 3 - 5 - 7 - 23
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+16=2417 divisore nessuno
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

2401+18=2419 divisore 41
3-5-7-11-13-17-19-23-29-31-37-41-43-47.

Etc… fino al numero 2401+198



Ora. Rimanendo nella dimensione di X=200 proviamo ad analizzare una sotto dimensione di sole 5 unità

2401+2=2403 divisore 3
2401+4=2405 divisore 5 - 13 - 37
2401+6=2407 divisore 29
2401+8=2409 divisore 3 - 11
2401+10=2411 divisore nessuno

In questa sotto dimensione che chiameremo Y, poniamo Y=10, analizziamo i divisori e vediamo che di questi 14 divisori contenuti nella dimensione X=200, in questa sotto dimensione Y=10, ne troviamo solo 6. 3-5-11-13-29-37.

La domanda è… E se io per testare questi numeri dispari da 2401+2 a 2401+10 avessi usato solo quei 6 divisori, anziché 14, sicuramente ci avrei messo meno tempo e avrei avuto lo stesso risultato e cioè scoperto che il numero 2401+10 è un numero primo.

Come faccio a sapere quali divisori nella sotto dimensione Y=10 soddisfano la mia ricerca?

Mi faccio aiutare dalla funzione Modulare in questo modo.

A=2401 Mod(3)=1
Utilizzo il modulo per definire se A è dispari o pari A Mod(2)
se A Mod(2)=0 B=(-A)+3*2
se A Mod(2)<>0 B=(-A)+3
Se B Se B>=Y B verrà ignorato

A=2401 Mod(5)=1
se A Mod(2)=0 B=(-A)+5*2
se A Mod(2)<>0 B=(-A)+5
Se B Se B>=Y B verrà ignorato

A=2401 Mod(7)=0
se A Mod(2)=0 B=(-A)+7*2
se A Mod(2)<>0 B=(-A)+7
Se B Se B>=Y B verrà ignorato

Etc… Fino a interpellare tutti i 14 divisori primi della dimensione X=200

Alla fine otterrò un file dei soli divisori che interessano alla sotto dimensione di Y=10, dopo di ché sarà molto facile stabilire entro questa sotto dimensione quali numeri sono primi e quali sono composti.

Vi lascio qui sotto i dati degli esperimenti fatti su 1.320.690.920 divisori, solo numeri primi, in una dimensione totale di 30.499.999.951^2 – 30.499.999.949^2 = 121.999.999.800





ora inizio = 11:18:28.881923
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949


930249996889000002689
930249996889000002697
930249996889000002701
930249996889000002707
930249996889000002767
930249996889000002829
930249996889000002877
930249996889000002977
930249996889000003037
930249996889000003061
930249996889000003091
930249996889000003259
930249996889000003289
930249996889000003309
930249996889000003319
930249996889000003327
930249996889000003339
930249996889000003483
930249996889000003543
930249996889000003577
Numero divisori primi interpellati 1.320.690.920
ora fine = 11:49:03.758468

Divisori utilizzati 776 Su 1.320.690.920 totali in una sotto dimensione di Y=1.000
Da N= 930249996889000002601 a N+Y 930249996889000003601
Trovati 20 Numeri primi

Solo in questa prova vi posto tutti i numeri primi trovati, per le altre prove non avrei abbastanza spazio per postarle.

--------------------------------------------------------------------------------------------
ora inizio = 12:35:11
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
Numero primi letti 1.320.690.920
ora fine = 13:06:25

Divisori utilizzati 5895 Su 1.320.690.920 totali, in una sotto dimensione di Y=10.000
Da N= 930249996889000002601 a N+Y 930249996889000012601
Trovati 217 Numeri primi
---------------------------------------------------------------------------------------------

ora inizio = 13:14:20
ricerca del numero N=930249996889000002601, Cifre 21, Limite ricerca SQRT(N)=30.499.999.949
Numero primi letti 1.320.690.920
ora fine = 13:44:42

Divisori utilizzati 45427 Su 1.320.690.920 totali, in una sotto dimensione di Y=100.000
Da N= 930249996889000002601 a N+Y 930249996889000102601
Trovati 2084 Numeri primi
----------------------------------------------------------------------------------------------------

Questo è l’algoristmo scritto in Python
dove divi=Divisore, dove ni= 930249996889000002601

div1=ni%divi

if div1%2==0:
div2=(-div1)+divi*2
else:
div2=(-div1)+divi

if div2<=massimo:
scrivi.write(str(divi)+'\n')

Grazie

[hydro1]

Ovviamente non si capisce nulla, ma sembra sempre una variazione sul tema crivello di Eratostene. Ma al di là di questo devi sempre chiederti: è un algoritmo più rapido di quelli che esistono? Quanto ci mettono Magma, Sage, Pari/GP a fare la stessa cosa?

[claugoru]

Mi dispiace se non riesci a capire. Non credo di essermi espresso male o in cirillico.
Leggi bene e senza fretta e vedrai che c'è una bella differenza sulle ricerche che tu hai citato.
Puoi interpretarlo come crivello di Eratostene perchè non ho inventato niente di nuovo, diciamo chè ho trovato una strada più corta e un notevole risparmio di tempo.
Solo per farti un esempio... Se tu con un pc cerchi i numeri primi nei primi 1000 numeri, ottieni questi numeri primi con una velocita supersonica. Questo sistema agisce come se tu dovessi controllare questi 1000 numeri ma in una dimensione molto più alta.

[claugoru]

Un'altra cosa. Prima di impegnare un calcolatore nella ricerca di un numero primo, c'è la necessita di fare dei test probabilistici o test di primalità per escludere, in una percentuale molto bassa, che dopo centinaia o migliaia di ore di lavoro questo numero non risulti composto. In questo caso non necessita fare test perchè il numero che io analizzo è certamente un composto. Ma l'analisi di questo numero mi porterà a conoscenza di molti altri numeri in cui ci sarà certamente un numero primo

[hydro1]

"claugoru": diciamo chè ho trovato una strada più corta e un notevole risparmio di tempo.

Bravo, questa è la domanda. Hai fatto dei test con il tuo algoritmo contro quelli implementati dai sistemi moderni di algebra simbolica? Altrimenti come fai a sapere che c'è un notevole risparmio di tempo?

"claugoru":Un'altra cosa. Prima di impegnare un calcolatore nella ricerca di un numero primo, c'è la necessita di fare dei test probabilistici o test di primalità per escludere, in una percentuale molto bassa, che dopo centinaia o migliaia di ore di lavoro questo numero non risulti composto. In questo caso non necessita fare test perchè il numero che io analizzo è certamente un composto.

Questo è irrilevante rispetto al running time perchè i test probabilistici di primalità sono rapidissimi e anche tra quelli deterministici ne esistono che vanno in tempo polinomiale.

[claugoru]

"hydro":[quote="claugoru"] diciamo chè ho trovato una strada più corta e un notevole risparmio di tempo.

Bravo, questa è la domanda. Hai fatto dei test con il tuo algoritmo contro quelli implementati dai sistemi moderni di algebra simbolica? Altrimenti come fai a sapere che c'è un notevole risparmio di tempo?

"claugoru":Un'altra cosa. Prima di impegnare un calcolatore nella ricerca di un numero primo, c'è la necessita di fare dei test probabilistici o test di primalità per escludere, in una percentuale molto bassa, che dopo centinaia o migliaia di ore di lavoro questo numero non risulti composto. In questo caso non necessita fare test perchè il numero che io analizzo è certamente un composto.

Questo è irrilevante rispetto al running time perchè i test probabilistici di primalità sono rapidissimi e anche tra quelli deterministici ne esistono che vanno in tempo polinomiale.[/quote]

Certo che ho fatto dei test e alcuni sono quelli riportati nel post. Per quanto riguarda i test probabilistici non sono così veloci come pensi, soprattutto nei numeri molto grandi. Ora però mi rispondi a una domanda semplice, per favore. Supponi di voler verificare che un numero di 500 cifre sia realmente primo, come fai? Fai un test tipo Rabin-Miller e ottieni una validità con 1/4 o 1/16 di probabilità che non lo sia. Adesso però mi devi dimostrare che quel numero è effettivamente primo perchè 1/4 o un 1/16 di errore non mi danno la certezza che sia così.
Come fai?
Altra cosa... Quanto tempo ci mette un elaboratore per quanto super potente a darmi un numero primo di 500 o più cifre? Un paio di secondi? un paio minuti? un paio d'ore, un paio di giorni? Quanto?
Grazie per la risposta

[hydro1]

"claugoru":

Certo che ho fatto dei test e alcuni sono quelli riportati nel post.

Ma contro quali sistemi hai testato il tuo algoritmo? Contro Magma? Sage? Matlab? Non si evince dal tuo post.

"claugoru":
Per quanto riguarda i test probabilistici non sono così veloci come pensi, soprattutto nei numeri molto grandi.

Dipende dal test che vuoi fare, ma in ogni caso la complessità è polinomiale.

"claugoru":
Adesso però mi devi dimostrare che quel numero è effettivamente primo perchè 1/4 o un 1/16 di errore non mi danno la certezza che sia così.
Come fai?

Così

"claugoru":
Altra cosa... Quanto tempo ci mette un elaboratore per quanto super potente a darmi un numero primo di 500 o più cifre? Un paio di secondi? un paio minuti? un paio d'ore, un paio di giorni? Quanto?

Ah io non ne ho idea ma sei tu che hai detto che il tuo metodo porta un notevole risparmio di tempo. Quindi mi aspettavo una risposta tipo: "a parità di processore il miglior algoritmo esistente ci mette 24 ore invece il mio 12", o qualcosa di simile. Ripeto la domanda: hai fatto un confronto del genere? E se non l'hai fatto, come fai a sapere che il tuo algoritmo è più veloce?

[claugoru]

Mi devi però fare un favore e cioè ragionare sul metodo e non sulla quantità. Nell progetto GIMPS nei numeri di mersenne sono coinvolti più di 200.000 computer sparsi per il mondo. Capisco che si tratta di numeri enormi, di milioni di cifre, ma c'è anche da dire che ci mettono degli anni per trovare uno di questo numeri enormi, e sempre se riescono a trovarlo. Io non ho potenza di calcolo e i miei calcoli si basano su un metodo e non sulla dimensione del numero. Posso dire con certezza che la cosa non cambierebbe e cioè un numero di 23 e un numero di 500 o più cifre, mi darebbe lo stesso risultato. Io però la potenza di calcolo per dimostrarlo non ce l'ho perciò parliamo, se ti va, su numeri più abbordabili e con un paragone che non sia tra un computer normale e un super computer ma tra due computer alla pari

[claugoru]

Facciamo un esempio pratico. Tu hai un processore I5 con 3.1GHz, riesci a trovare un numero primo di 21 cifre in 8 decimi di secondo? Lascia però perdere la probabilità che è primo, io voglio sapere se è primo al 100%

[hydro1]

E chi ha parlato di potenza di calcolo? Ho specificatamente detto “a parità di processore”. Sto parlando dell’algoritmo in se, non della macchina. Per questo ti ho detto prendi il tuo laptop e controlla quanto tempo ci mette Magma a fare la stessa cosa, no? Questo ti darà almeno un’indicazione: se Magma ci mette meno significa che ci sono algoritmi migliori del tuo.

"claugoru":Facciamo un esempio pratico. Tu hai un processore I5 con 3.1GHz, riesci a trovare un numero primo di 21 cifre in 8 decimi di secondo? Lascia però perdere la probabilità che è primo, io voglio sapere se è primo al 100%

Di nuovo non lo so ed è anche un problema mal posto perché dipende un po’ da dove lo vuoi cercare. Ma comunque ricordati che la probabilità che un numero “random” di 20 cifre sia primo e’ circa \(1/\log 20\), quindi non è così bassa. Il che mi fa sospettare che la risposta sia “sì”.

[claugoru]

Non conosco Magma ma se mi dai qualche indizio in più provo a guardarci.
Credo comunque sia inutile continuare a discutere sull'aspetto velocità. Ti do comunque un altro dato che non ho messo nel post e cioè che con lo stesso medesimo tempo e cioè 30 minuti di calcoli questo algoritmo ha
identificato in una dimensione di 500.000 numeri, 10375 numeri primi sicuri da 21 cifre. Direi che è un ottimo risultato. Con questo non voglio dire che è meglio degli altri, anzi me ne guardo bene, dico solo che lavora in modo diverso e basa il suo ragionamento sul fatto che ogni numero contiene una mappa pronta a svelare dove si trovano i numeri primi che lo seguono. Naturalmente tutto questo in una dimensione finita.

[hydro1]

"claugoru":Non conosco Magma ma se mi dai qualche indizio in più provo a guardarci.

Magma è solo un esempio, ci sono diversi software per la matematica astratta che fanno cose di livello piuttosto profondo. Altri esempi sono Sage e Pari/GP. Se google questi nomi troverai tutte le informazioni del mondo.

"claugoru":
Direi che è un ottimo risultato. Con questo non voglio dire che è meglio degli altri, anzi me ne guardo bene, dico solo che lavora in modo diverso

Questo è esattamente quello che ti sto contestando. Per dire che qualcosa è “un ottimo risultato” o che “lavora in modo diverso” è necessario avere contezza di quali siano gli altri metodi e gli altri risultati. Perché se poi scopri (non so se sia questo il caso, ma fossi in te io me lo domanderei) che esiste un algoritmo che viaggia al doppio della velocità del tuo, il risultato non è più ottimo. E se scopri che è un metodo che già esiste, non puoi più dire che “lavora in modo diverso”. Morale della favola: informati su quali algoritmi per la ricerca dei primi vengono usati dai software moderni, cosa abbastanza semplice perché in genere sta scritto nella documentazione, e poi compara il loro running time con il tuo.

[claugoru]

In realtà non sai niente di me e delle mie conoscenze nel campo della ricerca sui numeri primi. Al contrario se tu conosci un metodo per individuare i numeri primi con tanta facilità mi piacerebbe conoscerlo. Io posso solo dirti quello che secondo me è un ottimo sistema per trovare dei numeri primi, e poi fai tu. Anzi se lo vuoi sperimentare il post riporta l'algoritmo in python così ti fai un'idea personalmente.
Credimi però, se fosse così facile trovare numeri primi di grosse dimensioni, come quelli per esempio che si usano nella RSA per i codici criptati, non si parlerebbe così tanto di una ricerca sempre più affannosa per trovarne dei nuovi.
Solo un'ultima domanda. Tu sai quanti primi conosciamo e sono stati salvati sopra un supporto da 3 a 500 cifre?
Solo per darti una notizia in una università italiana hanno collezionato 8Tb di dati, numeri primi, che arrivano al massimo a 50 cifre, il che vuol dire che possono scovare in 48 ore circa un numero primo di 100/101 cifre. Siamo ancora molto lontani dalle cinquecento che richiede adesso la RSA per stare tranquilla.

Un altra cosa... Vorrei segnalarti questi due siti
https://it.numberempire.com/primenumbers.php

https://wims.univ-cotedazur.fr/wims/wim ... 0000000877

Nel primo metti dentro un numero fino a 200 cifre e ti dice immediatamente se è primo o no
Nel secondo altrettanto con solo la differenza che è un poco più serio perchè ti dice che si, é un probabile numero primo.

Per me da probabile a certo passa un po' di differenza, Non trovi?

[hydro1]

"claugoru":In realtà non sai niente di me e delle mie conoscenze nel campo della ricerca sui numeri primi.Anzi se lo vuoi sperimentare il post riporta l'algoritmo in python così ti fai un'idea personalmente.

No non lo so e non mi interessa neanche tanto perchè non è questo il punto del discorso. Il punto è semplicemente che quando si comunica una scoperta scientifica, di qualunque tipo e in qualunque campo, la frase "la mi scoperta è meglio di altre cose" va motivata, altrimenti non significa nulla. Tu hai scritto che il tuo metodo da un notevole risparmio di tempo. Non sto criticando questa affermazione, ti sto chiedendo un risparmio rispetto a che cosa?

"claugoru":
Io posso solo dirti quello che secondo me è un ottimo sistema per trovare dei numeri primi, e poi fai tu.

E io posso dirti che sono un ottimo cantante country, e allora?

"claugoru":
Solo un'ultima domanda. Tu sai quanti primi conosciamo e sono stati salvati sopra un supporto da 3 a 500 cifre?

No, e davvero non mi interessa.

"claugoru":
Per me da probabile a certo passa un po' di differenza, Non trovi?

Ho mai affermato il contrario?

[claugoru]

[/quote]Il punto è semplicemente che quando si comunica una scoperta scientifica, di qualunque tipo e in qualunque campo, la frase "la mi scoperta è meglio di altre cose" va motivata, altrimenti non significa nulla[quote]

Niente di tutto ciò, nessuna scoperta scientifica. Se fosse stata tale non l'avrei certo enunciata in un forum
Innanzi tutto non credo di aver mai parlato di mia scoperta, casomai ho parlato di metodo.
Secondo, si, ho affermato che con questo metodo si potrebbero evitare i test probabilistici o test di primalità, ma a questo tu non hai mai risposto, probabilmente perchè alla fine non ti interessa e volevi solo polemizzare.

Tranquillo, il mio scopo era solo di dare uno spunto a un modo diverso di interpretare la ricerca di questi numeri.

[hydro1]

"claugoru":
Niente di tutto ciò, nessuna scoperta scientifica.

E perchè no? Se pensi che sia un metodo nuovo certamente si qualifica come una scoperta.

"claugoru":
Secondo, si, ho affermato che con questo metodo si potrebbero evitare i test probabilistici o test di primalità, ma a questo tu non hai mai risposto, probabilmente perchè alla fine non ti interessa e volevi solo polemizzare.

Questo l'ho capito, ma la mia domanda è un'altra: tu sei sicuro che 1) i metodi che vengono usati correntemente si basino su dei test di primalità? e 2) se la risposta a 1) è sì, sei sicuro che sia più efficiente il tuo metodo piuttosto che un metodo diverso che usa un test deterministico di primalità? E soprattutto, se non conosci la riposta a 1) e 2), come fai ad affermare che il tuo metodo è ottimo?

[claugoru]

[/quote]Questo l'ho capito, ma la mia domanda è un'altra: tu sei sicuro che 1) i metodi che vengono usati correntemente si basino su dei test di primalità? e 2) se la risposta a 1) è sì, sei sicuro che sia più efficiente il tuo metodo piuttosto che un metodo diverso che usa un test deterministico di primalità? E soprattutto, se non conosci la riposta a 1) e 2), come fai ad affermare che il tuo metodo è ottimo?[quote]

il mio pensiero si basa su un ragionamento logico.

1) La distribuzione dei numeri primi è ancora un mistero e credo lo rimarrà ancora per molto in quanto le variabili in campo sono talmente tante che anche un super super elaboratore non riuscirebbe a metterle insieme.
2) Quando nell'antichità scoprirono che alcuni numeri non potevano essere divisi in un intero si chiesero il perchè e scoprirono in poco tempo che alcuni numeri potevano essere divisi solo per 1 e per se stessi. Questo diede vita alla ricerca di questo fenomeno e scoprirono che per capire quali numeri avevano questa proprietà bisognava dividerli per tutti i numeri che lo precedevano e se non trovavano un divisore che potesse dividerlo in un intero, questo era considerato un numero primo.
3) L'evoluzione di questa ricerca ci ha portati al secolo scorso, e quello prima, dove sono nati, dalla mente geniale di alcuni matematici, degli algoritmi che cercavano di individuare dove cadessero questi numeri così particolari. Anche perchè il calcolo manuale della divisone prima e poi della moltiplicazione(crivello) erano diventati molto pesanti da eseguire a mano. Test di Fermat e il test di Wilson, test di Lucas-Lehmer per i numeri di mersenne, test di Proth, test di Miller-Rabin è invece probabilistico che è anche uno dei più usati.
3) L'evoluzione del computer e le menti geniali di questa generazione hanno portato questa ricerca e migliorato alcuni di questi test a un livello mai raggiunto. Questo tipo di ricerca però continua a chiamarsi test, e si chiamerà sempre test fino a quando qualcuno non scoprirà la distribuzione di questi numeri.
4) Il test di primalità o probabilistico è molto ma molto più veloce che una ricerca su tutti i divisori primi che precedono N fino alla sua radice, ma alla fine è sempre un test, e per quanto bassa sia la sua percentuale di errore 1/4 1/16, è pur sempre un errore che bisogna considerare.

Ora, possiamo elaborare tutte le forme che vuoi per definire con certezza assoluta che il numero analizzato sia un numero primo che comunque sia hai bisogno di fare dei calcoli astronomici per avere questa certezza, e proprio per non buttare al vento tutto questo lavoro e soldi, ti appoggi a un test adatto alla tua ricerca per stabilire se il numero preso in esame potrebbe essere veramente primo.

Io mi sono solo chiesto, se questo numero che reputi un probabile primo, mentre fai tutti quei calcoli che ti porteranno a dire se lo sia effettivamente, non potresti sfruttare questa fatica per mappare in una dimensione finita quei numeri che si trovano vicino?

[hydro1]

"claugoru":Questo tipo di ricerca però continua a chiamarsi test, e si chiamerà sempre test fino a quando qualcuno non scoprirà la distribuzione di questi numeri.

Aaah ok, siamo tornati alla solita storia di "scoprire la distribuzione dei primi". Va bene avete vinto voi, ci rinuncio.

[claugoru]

Aaah ok, siamo tornati alla solita storia di "scoprire la distribuzione dei primi". Va bene avete vinto voi, ci rinuncio.

Scoprire la distribuzione dei numeri primi? Mi chiedo se sai leggere o se solo non sai cosa rispondere.

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

Se ho capito bene il tuo algoritmo, stai usando un metodo della teoria dei crivelli per cercare i numeri composti su una base di fattorizzazione, ci sono già algoritmi che fanno questo. Per esempio il rational sieve, o il più generale GNFS (General number field sieve) che è sostanzialmente una generalizzazione del precedente, adattando il metodo ad un campo numerico e al suo anello degli interi. Se ti interessa, il GNFS è il miglior algoritmo in termini di efficienza per fattorizzare numeri composti. E fattorizza numeri composti in un tempo subesponenziale ma sup-polinomiale. Anche se non possono essere utilizzati per fattorizzare potenze di numeri primi, però in questo caso è banale da fare in tempo logaritmico.

Per quanto riguarda

"hydro":[quote="claugoru"]Questo tipo di ricerca però continua a chiamarsi test, e si chiamerà sempre test fino a quando qualcuno non scoprirà la distribuzione di questi numeri.

Aaah ok, siamo tornati alla solita storia di "scoprire la distribuzione dei primi". Va bene avete vinto voi, ci rinuncio.[/quote]

"claugoru":
Scoprire la distribuzione dei numeri primi? Mi chiedo se sai leggere o se solo non sai cosa rispondere.

Non penso che hydro volesse dire che tu stavi asserendo di voler scoprire la distribuzione dei numeri primi. Penso si stesse riferendo semplicemente al fatto che è una domanda/affermazione un po' mal posta. Se hai una distribuzione allora potresti rispondere alla domanda: qual è la probabilità che scelto un intero positivo in modo casuale esso sia primo?
Purtroppo non esiste un modo per scegliere un intero positivo in modo tale che ciascun intero abbia la stessa probabilità di essere scelto, quindi è un problema posto un po' male.
Generalmente si passa per la densità naturale, ovvero consideri il problema su \( \{ 1 , \ldots, n \} \) dove è possibile fare ciò, definisci tale probabilità qui, e poi passi al limite.
Comunque sia in questo caso già si sa molto, il teorema dei numeri primi asserisce infatti che \( \pi(x) \sim x/\ln x \). Dunque la probabilità che un numero scelto casualmente in \( \{1, \ldots, n \} \) è primo è asintoticamente uguale a \( 1/ \ln n \). Una migliore approssimazione di \( \pi(x) \) è \( \Li(x) \).

[claugoru]

Se ho capito bene il tuo algoritmo, stai usando un metodo della teoria dei crivelli per cercare i numeri composti su una base di fattorizzazione

Più o meno. L'algoritmo testa un numero dispari, primo o composto, e traccia una mappa dei soli divisori che interessano una determinata dimensione. Il vantaggio consisterebbe nell' individuare e poi utilizzare questi pochi divisori per sondare questa dimensione e avere così la certezza dei numeri primi trovati.

Per tornare a noi, concordo che il crivello dei campi è attualmente l'algoritmo di fattorizzazione più veloce, che il metodo Miller-Rabin (Probabilistico) sia il metodo più veloce per dimostrare che un determinato numero è composto o probabilmente primo.

Concordo su tutto ma...
Vorrei solo che tu mi rispondessi a una cosa. Suppponiamo che tu abbia un numero primo di 300 cifre e lo elevi al quadrato ottenendo un prodotto di 600/601 cifre. Come risolvi il dubbio che questo numero da 600/601 non sia primo?
Naturalmente questo numero di 300 cifre potrebbe essere molto più grande e darti come risultato un prodotto molto più grande, perciò non fermiamoci alle parole ma atteniamoci ai concetti.

Io farei...
1) testo questo prodotto al fine di stabilire in tempi non biblici se non è appunto un composto
2) passo alla seconda fase, nel caso il test mi abbia dato come risultato negativo su un numero composto, effettuo una ricerca per determinare se esiste un probabile divisore primo che ha dato vita a questo prodotto.
Come faccio questa ricerca, dipende, uso un setaccio o setaccio quadrico, o qualsiasi crivello ci sia in circolazione, ma comunque so che non posso tralasciare nessuno dei potenzaili divisori o moltiplicatori fino alla radice di questo numero altrimenti rischio di certificare un numero primo che non è effetivamente primo.

Grazie