Scomposizione in fattori di un semiprimo

Messaggioda avinerba » 28/12/2007, 19:25

Così, per pura curiosità, qualcuno di voi è appassionato o interessato o ha mai dedicato qualche ora/giorno allo studio della scomposizione in fattori (primi) di un semiprimo?

Siete giunti a risultati interessanti, avete mai elaborato un vostro sistema? Una ipotesi?

Sono curioso.

Ciao.
avinerba
Starting Member
Starting Member
 
Messaggio: 5 di 15
Iscritto il: 16/07/2007, 11:12

Messaggioda yurifrey » 28/12/2007, 20:15

Io ne so poco, però se esistesse un sistema che permette di scomporre in due numeri primi $p$ e $q$ un semiprimo $n=p.q$ crollerebbe tutta la crittografia RSA. Credo che sia un problema che si è posto parecchia gente :D
Avatar utente
yurifrey
Junior Member
Junior Member
 
Messaggio: 82 di 106
Iscritto il: 23/08/2006, 10:22

Messaggioda avinerba » 29/12/2007, 10:02

yurifrey ha scritto:Io ne so poco, però se esistesse un sistema che permette di scomporre in due numeri primi $p$ e $q$ un semiprimo $n=p.q$ crollerebbe tutta la crittografia RSA. Credo che sia un problema che si è posto parecchia gente :D


RSA sicuramente andrebbe giù, ma non sarebbe la sola. I semiprimi vengono utilizzati in molte applicazioni, ad esempio in algoritmi per la generazione di numeri pseudocasuali. La validità di questi sistemi si basa appunto sulla difficoltà di fattorizzare un semiprimo molto grande.

Sono mesi ormai che ci lavoro, ho preso come campione circa 500.000 semiprimi e li ho studiati, cercando di delineare delle proprietà. Un approccio diverso, sicuramente molto informatico e non matematico, d'altronde il mio lavoro è quello di sistemista.

In italiano non ho trovato molti testi su internet, mentre in inglese ho trovato molto materiale valido.

Ormai per me è una passione, infatti ho scritto questo topic, per sapere se qualcuno si è mai appassionato, anche solo per un breve periodo a questo argomento.

Riprendo il lavoro, ciao!
avinerba
Starting Member
Starting Member
 
Messaggio: 6 di 15
Iscritto il: 16/07/2007, 11:12

Messaggioda avinerba » 23/01/2008, 10:42

Oggi ho terminato la prima parte della mia ricerca.

Sono molto imbarazzato, poichè ho deciso di pubblicarla e spero di non aver perso 6 mesi di tempo libero, in un qualcosa di "già fatto".

Durante questi sei mesi, ho cercato su internet ovunque, per capire se stavo percorrendo una strada già asfaltata da qualcuno.

Ritornando a prima, ora stò preparando la relazione, sono 4 quaderni che devo riassumere nel miglior modo possibile.

La ricerca l'ho ampliata a circa 200 milioni di semiprimi. Fortuna che sono un IT, su questo almeno sono avvantaggiato. Invece non sono un matematico e lo scetticismo riscontrato in generale (non qui sul forum, ma via mail, con alcuni matematici), lo capisco.

L'approccio sperimentale non è sicuramente tra i più apprezzati ma i risultati ci sono e credo, anzi spero, che sei mesi di ricerche non siano stati inutili, dato che i semiprimi trattati, vengono fattorizzati nel giro di pochi secondi.

Attualmente il lavoro procede, nello sviluppo di un algoritmo di fattorizzazione denominato QSX (Le iniziali QS non centrano niente con il Quadratic Sieve) che estende l'insieme di semiprimi fattorizzabili tramite questo sistema.

Al momento della pubblicazione, sarò felice, di pubblicare un link anche su questo forum, che stimo molto.

Spero di terminare questa prima parte, nel giro di due settimane.
Ultima modifica di avinerba il 14/01/2010, 08:33, modificato 1 volta in totale.
avinerba
Starting Member
Starting Member
 
Messaggio: 9 di 15
Iscritto il: 16/07/2007, 11:12

Messaggioda Ravok » 29/01/2008, 20:32

I sistemi per fattorizzare in numeri primi esistono eccome.. Ma RSA non cade perchè fattorizzare numeri con migliaia di cifre non richiede proprio due secondi... :D
Non si può essere entrambe le cose...(ik)
Ravok
Junior Member
Junior Member
 
Messaggio: 156 di 171
Iscritto il: 29/09/2006, 16:49

Messaggioda avinerba » 30/01/2008, 10:03

Ravok ha scritto:I sistemi per fattorizzare in numeri primi esistono eccome.. Ma RSA non cade perchè fattorizzare numeri con migliaia di cifre non richiede proprio due secondi... :D


Gli attuali sistemi di fattorizzazione, richiedono l'utilizzo di cluster dedicati con grandi capacità di calcolo e nonostante, la disponibilità di tale potenza, i tempi per scomporre un grande semiprimo sono nell'ordine di mesi o addirittura anni.

Nel 2007, esattamente, il 21 Maggio, è stato fattorizzato un numero di Mersenne, 1039 bit, un numero composto da 313 cifre decimali:

http://www.loria.fr/~zimmerma/records/21039-

Sono rimasto perplesso, dall'entusiasmo che è stato dato a questa scoperta, in quanto, uno dei fattori è molto piccolo, appena 7 cifre.

Guardando comunque al concorso (ormai chiuso) indetto dall'RSA, per il momento, la fattorizzione dei semiprimi proposti nel challenge, è ancora ferma a RSA-200 (fattorizzato nel maggio 2005), ovvero ad un semiprimo composto da 200 cifre decimali.

RSA, utilizza semiprimi composti da due numeri primi di grandezza identica o quasi. Per cui fattorizzare un numero RSA è sicuramente più difficile, che fattorizzare un qualsiasi semiprimo (o non), che contiene un fattore piccolo nell'ordine di poche cifre decimali.
avinerba
Starting Member
Starting Member
 
Messaggio: 10 di 15
Iscritto il: 16/07/2007, 11:12

Messaggioda vl4d » 30/01/2008, 12:26

Non ho capito il senso di questo topic... stai dicendo che hai sviluppato un algoritmo per
la fattorizzazione di interi con complessita' in tempo minore di quella del GNFS ?
Go to the roots, of these calculations! Group the operations.
Classify them according to their complexities rather than their appearances!
This, I believe, is the mission of future mathematicians. This is the road on which I am embarking in this work.
Evariste Galois
Avatar utente
vl4d
Average Member
Average Member
 
Messaggio: 505 di 515
Iscritto il: 05/05/2006, 14:49

Messaggioda avinerba » 01/02/2008, 15:34

vl4d ha scritto:Non ho capito il senso di questo topic... stai dicendo che hai sviluppato un algoritmo per
la fattorizzazione di interi con complessita' in tempo minore di quella del GNFS ?


Si.

Attualmente l'algoritimo, non tratta qualsiasi semiprimo, ma un gruppo, un insieme ben definito.

I tempi di scomposizione, sono nell'ordine di secondi. Non è legato alla grandezza del semiprimo da scomporre, la sua efficienza è costante, pur lavorando con semiprimi molto grandi, attualmente stò sperimentando, semiprimi nell'ordine di 300 cifre decimali (nessun numero del challenge RSA).

Quella che ho terminato è la prima fase del lavoro che ho iniziato 6 mesi fa, durante il quale, ho potuto testare l'algoritmo su un campione totale, ad oggi di 350 milioni di semiprimi e ho analizzato i primi 15 milioni di primi. Adesso i test, si sono spostati "in alto", su semiprimi a partire da 200 cifre decimali.

L'evoluzione dello studio portato avanti fino ad oggi, si chiama QSX. Come ho scritto, non ha alcun legame con il Quadratic Sieve, sebbene le iniziali QS, possano trarre in inganno.

Sono soddisfatto del lavoro fatto, dato che stò terminando la prima parte della relazione che spiega nel dettaglio le basi di QSX. A questo punto, i prossimi obiettivi sono la scompozione dei numeri di Mersenne e di Fermat (ciò può avvenire solo se sono numeri composti e non primi). Per i numeri di Mersenne, c'è ancora molto da fare, visto che alcuni (tanti) non sono stati ancora scomposti, riguardo ai numeri di Fermat, ad oggi non sono stati trovati ulteriori primi, per cui anche qui, c'è da fare.

Una prima versione di QSX l'ho testata anche su numero RSA-1024, ma era una versione ancora "primitiva". A breve, devo riscrivere QSX e questa volta, il test riguarderà la serie completa di numeri RSA del challenge (ormai chiuso) ancora non scomposti.

Il senso di questo topic è quello di conoscere qualcun altro, che come me, si è appassionato a questo settore e magari, ha sviluppato nel tempo, un idea, un progetto valido, sulla scomposizione di semiprimi.

Purtroppo ho appurato che in Italia, non c'è molta passione nel campo della Teoria dei Numeri. Non essendo un matematico, trovo anche difficoltà ad essere preso sul serio, in quanto lo scetticismo è (giustamente) tanto, sebbene, il mio lavoro non è una serie di formule o concetti astratti, ma è convalidato da una ricerca sperimentale seria e ben documentata.

A questo punto, infatti, preso atto di questa situazione, punto a cercare di fornire una prova importante, per ottenere un po' di attenzione e credo che l'unico modo sia quello di puntare a scomporre un RSA oppure qualche numero di Mersenne particolarmente grande, come hanno fatto nel Maggio 2007.

Comunque l'algoritmo QSX è scritto nel linguaggio proprietario di Maxima, per cui una volta divulgato, senza tante parole, chiunque scaricandosi gratuitamente Maxima ( http://maxima.sourceforge.net/ ) potrà testarlo e trarre le proprie conclusioni. Uso Maxima, poichè è abbastanza semplice da usare e posso trattare adeguatamente numeri molto grandi, con molte cifre. Lo studio iniziale, nei primi mesi dei semiprimi sotto le 15 cifre, l'ho realizzato interamente in classic ASP, usando come database MYSQL 5.x, con il quale posso gestire tabelle molto grandi (quella con i 200 milioni di semiprimi è quasi 7GB).
Ultima modifica di avinerba il 14/01/2010, 08:33, modificato 1 volta in totale.
avinerba
Starting Member
Starting Member
 
Messaggio: 11 di 15
Iscritto il: 16/07/2007, 11:12

Messaggioda vl4d » 01/02/2008, 16:44

Rispetto le tue fatiche, le rispetto davvero tanto.
Pero' devi capire che non e' neanche lontanamente pensabile attaccare problemi del genere
senza usare la Matematica...
e' come voler giocare a calcio in serie A e ostinarsi a dire "ma io non voglio dare calci al pallone".
Quando ti chiedo la complessita' dell'algoritmo, io intendo la complessita' asintotica: dire
che un algoritmo "ci mette pochi secondi" non ha nessun significato. Spero che
tu non ti offenda per questo mio intervento, il mio scopo e' solo "dirottarti" sull'unica strada
percorribile, che si chiama Matematica. Purtroppo qualche libro di divulgazione non basta,
e molte volte fa piu' danni che altro:
ad esempio:
Non è legato alla grandezza del semiprimo da scomporre, la sua efficienza è costante


questo non e' possibile. Non e' possibile che la fattorizzazione richieda tempo $O(1)$ perche'
solo per leggere il semiprimo $n$ che vuoi fattorizzare e' necessario un numero di passi $O(\log n)$.
Go to the roots, of these calculations! Group the operations.
Classify them according to their complexities rather than their appearances!
This, I believe, is the mission of future mathematicians. This is the road on which I am embarking in this work.
Evariste Galois
Avatar utente
vl4d
Average Member
Average Member
 
Messaggio: 506 di 515
Iscritto il: 05/05/2006, 14:49

Messaggioda avinerba » 01/02/2008, 17:07

vl4d ha scritto:Rispetto le tue fatiche, le rispetto davvero tanto.
Pero' devi capire che non e' neanche lontanamente pensabile attaccare problemi del genere
senza usare la Matematica...
e' come voler giocare a calcio in serie A e ostinarsi a dire "ma io non voglio dare calci al pallone".
Quando ti chiedo la complessita' dell'algoritmo, io intendo la complessita' asintotica: dire
che un algoritmo "ci mette pochi secondi" non ha nessun significato. Spero che
tu non ti offenda per questo mio intervento, il mio scopo e' solo "dirottarti" sull'unica strada
percorribile, che si chiama Matematica. Purtroppo qualche libro di divulgazione non basta,
e molte volte fa piu' danni che altro:
ad esempio:
Non è legato alla grandezza del semiprimo da scomporre, la sua efficienza è costante


questo non e' possibile. Non e' possibile che la fattorizzazione richieda tempo $O(1)$ perche'
solo per leggere il semiprimo $n$ che vuoi fattorizzare e' necessario un numero di passi $O(\log n)$.


Non mi offendo, assolutamente. Come entro in un forum di matematica, so benissimo a cosa vado incontro.
Ultima modifica di avinerba il 01/02/2008, 17:43, modificato 1 volta in totale.
avinerba
Starting Member
Starting Member
 
Messaggio: 12 di 15
Iscritto il: 16/07/2007, 11:12

Prossimo

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: megas_archon e 1 ospite