Un algoritmo per trovare i fattori di n =pq con p, q primi
Ecco l'algoritmo http://www.box.net/shared/ivjnpmkvva che va ad aggiungersi ed ad integrarsi a quelli già descritti http://www.box.net/shared/elaetidb0n
raccolta completa su http://armellini.pbworks.com
raccolta completa su http://armellini.pbworks.com
Risposte
Ho dato una occhiata al tuo sito:
simpatica la generazione dei numeri primi.
simpatica la generazione dei numeri primi.
Ti ringrazio per le tue osservazioni. Il linguaggio C/C++ è un ottimo linguaggio di programmazione anche per sperimentare algoritmi numerici (come lo è ancor di più il fortran 90). E' vero i compilatori C/C++ non possono gestire numeri di oltre 15 cifre però il PARI/GP sì (ache 400 cifre) e il PARI/GP è gratuito ed usa un codice simile al C. Io ho scritto per ogni algoritmo anche la versione in PARI/GP. Su internet ci sono poi molte librerie gratuite (ma io non le so installare) che permetterebbero di gestire grandi numeri con i normali compilatori in C/C++. Il problema però è che i nostri PC hanno comunque una potenza di calcolo molto limitata non adatta per problemi RSA. In questi casi si usano supercalcolatori in parallelo molto costosi che lavorano per mesi. I miei algoritmi sono in parte riconducibili a varianti alla Fermat e in parte sono originali ma non si basano certo su idee rivoluzionarie bensì su semplici oservazioni (che però sono dimostrate). Sto sviluppando nuove procedure basate sulla geometria analitica. Appena pronte e verificate le pubblicherò.
Lo so come funziona RSA, ho fatto l'esame di Codici e Crittografia a Luglio (e qualcosa ancora ricordo 
).
Avevo mosso questa obiezione perché non avevo letto sul suo documento questa ipotesi.
Comunque non trovo idee rivoluzionarie, piuttosto continuo a lodare il lavoro massacrante svolto in ambito di programmazione...
Solo che non so quanto possa essere giusto confermare risultati o controllare ipotesi con algoritmi, per quel poco che so di C++ (adesso navigo in fortran90) mi pare che le variabili abbiano comunque una precisione numerica abbastanza limitata mentre per RSA si parla di numeri con almeno 300 cifre (in base 10)...
Mi ricordo che su un libro che ho letto una decina di volte o giù di lì (l'enigma dei numeri primi... "the sounds of primes" in inglese, un libro molto interessante) si dice "un mucchio di indizi non fa una prova"...
Piuttosto sarebbe interessante sentire il parere di altri forumisti che ne sanno molto più di me (e ce ne sono a centinaia...!)
).Avevo mosso questa obiezione perché non avevo letto sul suo documento questa ipotesi.
Comunque non trovo idee rivoluzionarie, piuttosto continuo a lodare il lavoro massacrante svolto in ambito di programmazione...
Solo che non so quanto possa essere giusto confermare risultati o controllare ipotesi con algoritmi, per quel poco che so di C++ (adesso navigo in fortran90) mi pare che le variabili abbiano comunque una precisione numerica abbastanza limitata mentre per RSA si parla di numeri con almeno 300 cifre (in base 10)...
Mi ricordo che su un libro che ho letto una decina di volte o giù di lì (l'enigma dei numeri primi... "the sounds of primes" in inglese, un libro molto interessante) si dice "un mucchio di indizi non fa una prova"...
Piuttosto sarebbe interessante sentire il parere di altri forumisti che ne sanno molto più di me (e ce ne sono a centinaia...!)
Mi scuso per qualche errore di battitura: è dovuto al fatto che non sempre ho tempo di rileggere attentamente il testo e di solito di concentro di più sugli aspetti matemtici. Quando considero W mi metto nell'ipotesi di numeri n = pq tipo RSA. In questi casi è molto improbabile che un fattore sia di piccole dimensioni, altrimenti sarebbe facile trovarlo. P e q inoltre non possono essere tropppo vicini a raq(n) perché anche in questo caso sarebbe troppo facile risolvere il problema della fattorizzazione. Se va a vedere i problemi RSA già risolti verificherà che questa proprietà è sempre verificata.
Per il resto tutto si può migliorare.
Per il resto tutto si può migliorare.
Buonasera,
sono appena appena tornato dall'università e ho trovato questo interessante thread aperto da lei su questo argomento.
Ho visitato la sua pagina dove c'è tutta la raccolta dei suoi elaborati e mi sono messo a leggerli.
Nel "teoria-numeri-primi.pdf" c'è una sua affermazione (pag.1)
>>Dato un numero $p$ da fattorizzare di $n$ cifre è facile provare che almeno un fattore deve essere dell'ordine di $W=10^{Int(n/2)-1}$, cioè deve avere almeno "int$(n/2)-1$ cifre" con "int(x)" la funzione parte intera di $x$ [nota: qui ha sbagliato a scrivere, ha scritto 2 volte "la parte"]. Se $p=ab$ con $a,b$ numeri primi, allora entrambi i fattori sono entrambi [nota: se fossi in lei eviterei di ripetere "entrambi"] maggiori di "W", cioè tali per cui $a>W, b>W$, cioè $S=a+b>W$.<<
Ora, a parte le critiche (costruttive, non voglio offendere nessuno, anzi!) dell'italiano, mi sento in dovere di muovere questa obiezione: se prendo un numero primo $a$ di 1000 cifre e lo moltiplico per $b=2$ che è comunque primo, ottengo $p=ab$ con $p$ dell'ordine (circa) di $10^1000$ dove, però, $b$ non è affatto maggiore di $W$ se lei come $W$ intende in questo caso $W=10^499$...
Il resto del documento l'ho praticamente saltato: di C e programmazione non ne so quasi nulla...
Nel "RSA.pdf" è interessante il suo modo di attaccare il problema, ma non mi sembra che si vada molto lontano: lascio i commenti ad altri che se ne intendono meglio.
Ho letto "Pigreco.pdf", "Pigreco - II.pdf", quello del numero di nepero, "integrali - probabil.pdf". Sono degli schemi interessanti per gli studenti che devono seguire analisi I o analisi numerica.
Arriviamo a "algoprimalità.pdf". Mi può spiegare per quale motivo si può sostituire int$(\sqrt(p))$ a $(p-1)!$?
L'ultimo è "un nuovo sistema di cifratura simmetrica dei dati.pdf". In esso c'è una frase:
>>... $det(c)<>1$ cioè $C$ sia invertibile...<<
Non l'ho analizzato di più perché non ho tempo, anzi, chiedo scusa per qualche mia svista.
Ci tengo a puntualizzare che le critiche sono positive, non intendo in nessun modo prendere in giro o altro, ma voglio soprattutto capire e meravigliarmi di fronte alla matematica che ogni giorno non cessa mai di stupirmi.
PS. Comunque ammiro davvero tutto lo sforzo profuso negli algoritmi: sono alle prese con il fortran90 e per far riportare un programmino ci metto un secolo...
sono appena appena tornato dall'università e ho trovato questo interessante thread aperto da lei su questo argomento.
Ho visitato la sua pagina dove c'è tutta la raccolta dei suoi elaborati e mi sono messo a leggerli.
Nel "teoria-numeri-primi.pdf" c'è una sua affermazione (pag.1)
>>Dato un numero $p$ da fattorizzare di $n$ cifre è facile provare che almeno un fattore deve essere dell'ordine di $W=10^{Int(n/2)-1}$, cioè deve avere almeno "int$(n/2)-1$ cifre" con "int(x)" la funzione parte intera di $x$ [nota: qui ha sbagliato a scrivere, ha scritto 2 volte "la parte"]. Se $p=ab$ con $a,b$ numeri primi, allora entrambi i fattori sono entrambi [nota: se fossi in lei eviterei di ripetere "entrambi"] maggiori di "W", cioè tali per cui $a>W, b>W$, cioè $S=a+b>W$.<<
Ora, a parte le critiche (costruttive, non voglio offendere nessuno, anzi!) dell'italiano, mi sento in dovere di muovere questa obiezione: se prendo un numero primo $a$ di 1000 cifre e lo moltiplico per $b=2$ che è comunque primo, ottengo $p=ab$ con $p$ dell'ordine (circa) di $10^1000$ dove, però, $b$ non è affatto maggiore di $W$ se lei come $W$ intende in questo caso $W=10^499$...
Il resto del documento l'ho praticamente saltato: di C e programmazione non ne so quasi nulla...
Nel "RSA.pdf" è interessante il suo modo di attaccare il problema, ma non mi sembra che si vada molto lontano: lascio i commenti ad altri che se ne intendono meglio.
Ho letto "Pigreco.pdf", "Pigreco - II.pdf", quello del numero di nepero, "integrali - probabil.pdf". Sono degli schemi interessanti per gli studenti che devono seguire analisi I o analisi numerica.
Arriviamo a "algoprimalità.pdf". Mi può spiegare per quale motivo si può sostituire int$(\sqrt(p))$ a $(p-1)!$?
L'ultimo è "un nuovo sistema di cifratura simmetrica dei dati.pdf". In esso c'è una frase:
>>... $det(c)<>1$ cioè $C$ sia invertibile...<<
Non l'ho analizzato di più perché non ho tempo, anzi, chiedo scusa per qualche mia svista.
Ci tengo a puntualizzare che le critiche sono positive, non intendo in nessun modo prendere in giro o altro, ma voglio soprattutto capire e meravigliarmi di fronte alla matematica che ogni giorno non cessa mai di stupirmi.
PS. Comunque ammiro davvero tutto lo sforzo profuso negli algoritmi: sono alle prese con il fortran90 e per far riportare un programmino ci metto un secolo...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo