Algoritmi sui numeri primi
Ho creato questi tre algoritmi e vorrei un vostro parere
http://albericolepore.altervista.org/crivello-lepore/
e
http://albericolepore.altervista.org/te ... ta-lepore/
e
http://albericolepore.altervista.org/co ... uccessivo/
http://albericolepore.altervista.org/crivello-lepore/
e
http://albericolepore.altervista.org/te ... ta-lepore/
e
http://albericolepore.altervista.org/co ... uccessivo/
Risposte
Buon Natale e benvenuto al forum.
Ho letto con interesse quello che hai scritto perché anche se sono distante dalla laurea, la teoria dei numeri resta sempre il mio più grande amore dopo la mia fidanzata.
Comunque, per il primo devo darti una grande delusione, e mi spiace perché non vorrei smorzare l'entusiasmo
Premesso che si può dimostrare che $p
ammetti di volere un numero primo di 500 cifre, cioè dell'ordine di $10^500$[nota]Verosimilmente di quelli che si usano oggi per gli algoritmi di crittografia a livello informatico, a meno che non sono rimasto indietro e ce ne sono anche di più grandi.[/nota]
Il tuo metodo impiega $n/3$ passi, cioè $n/3$ operazioni elementari per trovarlo, e dunque $(10^500)/3$ passi. Anche impiegasse $10^499$ (per difetto!) passi, è facile prevedere che un processore di 10GHz - cioè $10^10$ operazioni al secondo - impiegherebbe $10^489$ secondi per fare quel calcolo che sono tantini...
Il calcolo non è preciso, ma quello che conta è l'ordine di grandezza.
Il secondo, devo dire la verità, non l'ho capito ma non è questa una critica, magari stasera a pancia strapiena del cenone lo capirò meglio... oppure dormirò, non so quale delle due. Però anche qui dici
che purtroppo mi consente di darti un'altra delusione.
Non prendo numeri grandi per farti un dispetto, ma semplicemente perché sono quelli "standard" con cui si fanno applicazioni pratiche. Se prendiamo il solito primo dell'ordine di $10^500$, avresti un'ordine di grandezza di $10^250$ che è tantino anche in questo caso.
Il terzo è simile al secondo, quindi non l'ho afferrato molto bene, ma se non risponde qualcun altro - e mi fa capire anche a me
- se ho tempo mi ci rimetto su.
Comunque, la conclusione è questa.
Senza scomodare troppo la complessità computazionale, tanti risultati che si trovano o che hai trovato sono certamente interessanti ma non sono fattibili a livello pratico.
Poni, mi raccomando, l'accento tra la differenza di "impossibile" e "impossibile a livello pratico":
- impossibile vuol dire che non si può fare, che non esiste un metodo per fare (quello che è impossibile) e cose simili;
- impossibile al livello pratico vuol dire che teoricamente è impossibile, ma nella pratica non è agevole, non è efficace, non è fattibile e cose simili.
I tuoi algoritmi così come il crivello di Eratostene così come tanti altri algoritmi sui primi sono possibili, sono corretti - sul secondo e il terzo ho qualche dubbio ma ora la sto prendendo in generale - ma sono impossibili da attuare nella pratica. Se pensi di essere stato preso in giro perché ho preso numeri grandi pensa che gli algoritmi di firma digitale comuni sono del tipo "SHA1024" (o sigle simili con il numeretto alla fine), e pensa che quel "1024" indica che sono cifre dell'ordine di $2^1024$ cioè poco più di $10^300$.
Ho letto con interesse quello che hai scritto perché anche se sono distante dalla laurea, la teoria dei numeri resta sempre il mio più grande amore dopo la mia fidanzata.
Comunque, per il primo devo darti una grande delusione, e mi spiace perché non vorrei smorzare l'entusiasmo
"P_1_6, sul primo post dei tre link":
Il crivello di Lepore per trovare i p primi fino ad n ha bisogno di generare inizialmente n\3 numeri e per setacciare n/3-p .
Quindi avrà bisogno di n/3 +(n/3)-p per trovare i p primi fino ad n.
Premesso che si può dimostrare che $p
ammetti di volere un numero primo di 500 cifre, cioè dell'ordine di $10^500$[nota]Verosimilmente di quelli che si usano oggi per gli algoritmi di crittografia a livello informatico, a meno che non sono rimasto indietro e ce ne sono anche di più grandi.[/nota]
Il tuo metodo impiega $n/3$ passi, cioè $n/3$ operazioni elementari per trovarlo, e dunque $(10^500)/3$ passi. Anche impiegasse $10^499$ (per difetto!) passi, è facile prevedere che un processore di 10GHz - cioè $10^10$ operazioni al secondo - impiegherebbe $10^489$ secondi per fare quel calcolo che sono tantini...
Il calcolo non è preciso, ma quello che conta è l'ordine di grandezza.
Il secondo, devo dire la verità, non l'ho capito ma non è questa una critica, magari stasera a pancia strapiena del cenone lo capirò meglio... oppure dormirò, non so quale delle due. Però anche qui dici
"P_1_6, nel secondo post che ha linkato":
Quindi possiamo dire che tale procedimento per stabilire se un numero n è primo impiegherà al massimo (radice quadrata di (n))/3-1+2 ovvero (radice quadrata di (n))/3+1,
dove il-1 e lo 0,1666p e il +2 sono le divisioni per testare se n è divisibile per 2 e per 3.
che purtroppo mi consente di darti un'altra delusione.
Non prendo numeri grandi per farti un dispetto, ma semplicemente perché sono quelli "standard" con cui si fanno applicazioni pratiche. Se prendiamo il solito primo dell'ordine di $10^500$, avresti un'ordine di grandezza di $10^250$ che è tantino anche in questo caso.
Il terzo è simile al secondo, quindi non l'ho afferrato molto bene, ma se non risponde qualcun altro - e mi fa capire anche a me
- se ho tempo mi ci rimetto su.Comunque, la conclusione è questa.
Senza scomodare troppo la complessità computazionale, tanti risultati che si trovano o che hai trovato sono certamente interessanti ma non sono fattibili a livello pratico.
Poni, mi raccomando, l'accento tra la differenza di "impossibile" e "impossibile a livello pratico":
- impossibile vuol dire che non si può fare, che non esiste un metodo per fare (quello che è impossibile) e cose simili;
- impossibile al livello pratico vuol dire che teoricamente è impossibile, ma nella pratica non è agevole, non è efficace, non è fattibile e cose simili.
I tuoi algoritmi così come il crivello di Eratostene così come tanti altri algoritmi sui primi sono possibili, sono corretti - sul secondo e il terzo ho qualche dubbio ma ora la sto prendendo in generale - ma sono impossibili da attuare nella pratica. Se pensi di essere stato preso in giro perché ho preso numeri grandi pensa che gli algoritmi di firma digitale comuni sono del tipo "SHA1024" (o sigle simili con il numeretto alla fine), e pensa che quel "1024" indica che sono cifre dell'ordine di $2^1024$ cioè poco più di $10^300$.
Grazie per la tua riposta esauriente.
Ma volevo chiederti un'altra cosa:
potresti spiegarmi la differenza computazionale e di memoria tra
https://it.wikipedia.org/wiki/Crivello_di_Atkin
ed il mio
Ma volevo chiederti un'altra cosa:
potresti spiegarmi la differenza computazionale e di memoria tra
https://it.wikipedia.org/wiki/Crivello_di_Atkin
ed il mio
Fa parte di quella fascia ibrida tra:
- $O(n)$, quelli inefficaci;
- $O(log(n))$ quelli efficaci.
Non so cosa dire: senz'altro è più efficace e fattibile del tuo, ma non credo lo sia in senso assoluto. Facciamo il solito esempio con un primo di $10^500$ cifre, otteniamo come ordine di grandezza
$N/(log(log(n)))=(10^500)/(log(log(10^500))$
che wolframalpha dice essere circa $10^499$ (sempre come ordine di grandezza). Troppo anche qui (credo)...
Comunque ti consiglio di attendere risposte di altre menti migliori della mia.
- $O(n)$, quelli inefficaci;
- $O(log(n))$ quelli efficaci.
Non so cosa dire: senz'altro è più efficace e fattibile del tuo, ma non credo lo sia in senso assoluto. Facciamo il solito esempio con un primo di $10^500$ cifre, otteniamo come ordine di grandezza
$N/(log(log(n)))=(10^500)/(log(log(10^500))$
che wolframalpha dice essere circa $10^499$ (sempre come ordine di grandezza). Troppo anche qui (credo)...
Comunque ti consiglio di attendere risposte di altre menti migliori della mia.
In conclusione si può dire che nel frattempo il crivello di Atkin mette false a tutti gli n numeri il crivello di Lepore ha già trovato i p primi fino ad n.
Si può considerare vera questa affermazione?
Si può considerare vera questa affermazione?
ho aggiunto un piccolo aiuto per l'implementazione al crivello di lepore
un piccolo aiuto per l'implementzione
vediamo fino a 100 sono 32 operazioni di questo
5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 19+4=23, 23+2=25 25+4=29 ecc
i non primi li togli così
5*5; 25+30 ; 55+30;
5*7;35+30 ; 65+30;
7*7; 49+42;
7*11;
non capita in questo caso però si devono saltare i non primi fino alla radice quadrata di n quindi
(radice quadrata di n)/3-p1 dove p1 è il numero dei primi fino a (radice quadrata di n).
quindi sono 42 operazioni + l'aggiunta del 2 e del 3 che sono una costante
quindi in totale sono 44 operazioni
diciamo pure +5 se vogliamo metterci i capolinea
diciamo pure +2 per fare 6*5 e 6*7
in totale sono 51 operazioni elementari matematiche
vediamo fino a 100 sono 32 operazioni di questo
5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 19+4=23, 23+2=25 25+4=29 ecc
i non primi li togli così
5*5; 25+30 ; 55+30;
5*7;35+30 ; 65+30;
7*7; 49+42;
7*11;
non capita in questo caso però si devono saltare i non primi fino alla radice quadrata di n quindi
(radice quadrata di n)/3-p1 dove p1 è il numero dei primi fino a (radice quadrata di n).
quindi sono 42 operazioni + l'aggiunta del 2 e del 3 che sono una costante
quindi in totale sono 44 operazioni
diciamo pure +5 se vogliamo metterci i capolinea
diciamo pure +2 per fare 6*5 e 6*7
in totale sono 51 operazioni elementari matematiche
Ma in questo forum non c'è nessuno
Di questo che ne pensate?
X=fattore primo(incognita)
X^2+n(X*6)=numero rsa
per n che va da 1 a fino a quando non l'hai decodificato
e X che appartiene a quell'insieme di 5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 23+2=25 25+4=29 ecc oppure se vi è piu facile capire
0,8333 ; 1,1666 ;1,8333 ; 2,1666 ; ecc questi moltiplicati per 6
X=fattore primo(incognita)
X^2+n(X*6)=numero rsa
per n che va da 1 a fino a quando non l'hai decodificato
e X che appartiene a quell'insieme di 5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 23+2=25 25+4=29 ecc oppure se vi è piu facile capire
0,8333 ; 1,1666 ;1,8333 ; 2,1666 ; ecc questi moltiplicati per 6
L'altro pezzo lo avete capito?
Ho postato la soluzione per decodificsre l' RSA sulla home del blog.
che ne pensate?
che ne pensate?
vi posto le equazioni giuste ma credo che le avevate caoite
DECODIFICA RSA
con un range di n opportuno le tre equazioni per decodificare l’ RSA
X^2+n*(X*6)=numero rsa
2X^2+(6n+4)*X=numero rsa
2X^2+(6n+8)*X=numero rsa
X=fattore primo(incognita)
DECODIFICA RSA
con un range di n opportuno le tre equazioni per decodificare l’ RSA
X^2+n*(X*6)=numero rsa
2X^2+(6n+4)*X=numero rsa
2X^2+(6n+8)*X=numero rsa
X=fattore primo(incognita)
"P_1_6":
Applicando https://it.wikipedia.org/wiki/Teorema_dei_numeri_primi
ad n/3-p che ne esce fuori?
Non credo granché perché il teorema dei numeri primi è una stima del comportamento di $pi(n)$ e, come tutte le stime, inutile:
ne parlavo anche qui viewtopic.php?f=26&t=139863
"P_1_6":
un piccolo aiuto per l'implementzione
vediamo fino a 100 sono 32 operazioni di questo
5 , 5+2=7 , 7+4=11 ,11+2=13 , 13+4=17, 17+2=19, 19+4=23, 23+2=25 25+4=29 ecc
Purtroppo c'è sempre quel discorso di complessità computazionale che smonta gran parte di questi algoritmi. Non te lo dico per scoraggiarti o altro, ma semplicemente perché siamo in quella terra di mezzo dove regnano gli algoritmi corretti - anche carini e coccolosi[nota]Ho visto il film sui pinguini di Madagascar e ho riso per un'ora e mezzo![/nota] - ma impraticabili.
"P_1_6":
Ma in questo forum non c'è nessuno
A questo ti rispondo io dandoti un paio di motivazioni:
- la prima è che siamo sotto Natale e in molti hanno senz'altro una vita sociale... lontana da studio e lavoro;
- la seconda è che se ti sei iscritto, potresti dare un'occhiata al regolamento che vieta di scrivere un messaggio ogni due ore anche per un fatto di insistenza in un forum dove lo spirito regnante è la buona volontà.
Per il resto, io magari sarò ignorante (anche la lontananza dai tempi universitari farà il suo), però ti posso chiedere di dare un po' più ordine perché non ci ho capito moltissimo dei vari algoritmi.
Qualche utente meglio di me (come conoscenze) - e ce ne sono! - passerà, magari dopo le feste.
grazie zero87 per la tua risposta.
potresti darmi un parere su
potresti darmi un parere su
DECODIFICA RSA
con un range di n opportuno le tre equazioni per decodificare l’ RSA
X^2+n*(X*6)=numero rsa
2X^2+(6n+4)*X=numero rsa
2X^2+(6n+8)*X=numero rsa
X=fattore primo(incognita)
Ho detto che non ho capito molto e un po' d'ordine lo do io, correggimi se sbaglio a scrivere le tue idee - non sarebbe male che usassi le formule anche tu, per un fatto di leggibilità.
Allora tu dici
$x^2+n(6x)$ è RSA.
$2x^2+(6n+4)x$ è RSA.
$2x^2+(6n+1)x$ numero RSA.
$2x^2+(6n+8)$ numero RSA.
$x$ incognita.
Se non ho capito male, $x$ è quel numero periodico, cioè quel $1,\bar(6)$ o quella cosa simile del tuo algoritmo. Magari mi perdo qualcosa, ma non lo capisco molto quell'algoritmo come ho già detto ampiamente: consiglierei di aspettare altri utenti.
Allora tu dici
$x^2+n(6x)$ è RSA.
$2x^2+(6n+4)x$ è RSA.
$2x^2+(6n+1)x$ numero RSA.
$2x^2+(6n+8)$ numero RSA.
$x$ incognita.
Se non ho capito male, $x$ è quel numero periodico, cioè quel $1,\bar(6)$ o quella cosa simile del tuo algoritmo. Magari mi perdo qualcosa, ma non lo capisco molto quell'algoritmo come ho già detto ampiamente: consiglierei di aspettare altri utenti.
grazie finalmente qualcuno che riflette:
La prima è giusta
al posto di questa
provi X^2+(6n+2)*X=numero rsa
al posto di questa
provi X^2+(6n+4)*X=numero rsa
poi faccia una prova con tutti i possibili numeri RSA fino a quanto vuole
quando avrà capito che sono esatte passeremo ad n
La prima è giusta
al posto di questa
2X^2+(6n+4)*X=numero rsa
provi X^2+(6n+2)*X=numero rsa
al posto di questa
2X^2+(6n+8)*X=numero rsa
provi X^2+(6n+4)*X=numero rsa
poi faccia una prova con tutti i possibili numeri RSA fino a quanto vuole
quando avrà capito che sono esatte passeremo ad n
E se vi dicessi che la n si può scrivere in funzione di X.
Non appena qualcuno scriverà in uno dei forum “da quale parte del blog si ricavano queste equazioni” allora passeremo, per chi ancora non ha capito, alla spiegazione di n.
Cioè come n si scrive in funzione di X.
Non appena qualcuno scriverà in uno dei forum “da quale parte del blog si ricavano queste equazioni” allora passeremo, per chi ancora non ha capito, alla spiegazione di n.
Cioè come n si scrive in funzione di X.
[xdom="vict85"]Il regolamento prevede un up ogni 24 ore. In questa discussione hai spesso richiamato l'attenzione a poche ore una dall'altra. Nel seguito sei pregato di mostrare una maggiore pazienza.[/xdom]
le tre equazioni di n sono:(se non sbaglio)
n=(numero rsa – X^2)/(X*6)
n=(numero rsa – X*(X+2))/(X*6)
n=(numero rsa – X*(X+4))/(X*6)
Quindi dovete sostituirle nelle tre equazioni di sopra nello stesso ordine.
Quindi per decodificare un RSA c’è bisogno di sole tre equazioni.
Una di esse è quella giusta.
-------------------------------------------------------------------------------
Cerco conferme o smentite per favore
------------------------------------------------------------------------------
nella discussione nel forum di html.it qualcuno è stato così arduo da confermare
n=(numero rsa – X^2)/(X*6)
n=(numero rsa – X*(X+2))/(X*6)
n=(numero rsa – X*(X+4))/(X*6)
Quindi dovete sostituirle nelle tre equazioni di sopra nello stesso ordine.
Quindi per decodificare un RSA c’è bisogno di sole tre equazioni.
Una di esse è quella giusta.
-------------------------------------------------------------------------------
Cerco conferme o smentite per favore
------------------------------------------------------------------------------
nella discussione nel forum di html.it qualcuno è stato così arduo da confermare
In conclusione quindi possiamo dire che c’è bisogno di un algoritmo misto,
Come ho descritto sulla home del blog.
http://albericolepore.altervista.org/
grazie a tutti
Come ho descritto sulla home del blog.
http://albericolepore.altervista.org/
grazie a tutti
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo