Scomposizione in fattori di un semiprimo
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.
Siete giunti a risultati interessanti, avete mai elaborato un vostro sistema? Una ipotesi?
Sono curioso.
Ciao.
Risposte
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 
"yurifrey":
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
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!
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.
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.
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...
"Ravok":
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...
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.
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 ?
la fattorizzazione di interi con complessita' in tempo minore di quella del GNFS ?
"vl4d":
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).
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:
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)$.
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)$.
"vl4d":
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.
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)$.
Il costo operativo, a seconda del semiprimo che vado a trattare, in alcuni casi può essere pari a $O(1)$.
Il sistema si regge esclusivamente, su artimetica modulare e tabelle di valori, ricavate dal semiprimo che si intende scomporre in fattori. Cerco di riassumere 40 pagine, non è facile.
"avinerba":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)$.
Il costo operativo, a seconda del semiprimo che vado a trattare, in alcuni casi può essere pari a $O(1)$.
Il sistema si regge esclusivamente, su artimetica modulare e tabelle di valori, ricavate dal semiprimo che si intende scomporre in fattori. Cerco di riassumere 40 pagine, non è facile.
Vorrei porti io un problema... quanto ci metti a dire che il semiprimo è un semiprimo ed è dentro il gruppo che ti serve. Perché per farlo dovrai fare dei test...
Come si comporta il tuo algoritmo con gli altri numeri? Se il tuo numero controlla solo alcuni numeri per un algoritmo generale sarà necessario selezionare quelli che il tuo algoritmo può controllare e quello che il tuo non può e se questo elimina il vantaggio rispetto ad usare solo un algoritmo più generale il tuo algoritmo diventa inutile dal punto di vista pratico (dal punto di vista teorico dipende da cosa c'è scritto nell'articolo e non ho dubbi che possa essere interessante). La stessa cosa succede se il tuo gruppo è molto più piccolo del totale dei semiprimi (nonché dei numeri composti).
Aggiungo inoltre che se il tuo algoritmo è nell'ordine delle 10K (e probabilmente 5000 sono già tante) linee di codice la convenienza ad implementarlo e a provare ad ottimizzarlo ulteriormente sono molto ridotte.
Vorrei porti io un problema... quanto ci metti a dire che il semiprimo è un semiprimo ed è dentro il gruppo che ti serve. Perché per farlo dovrai fare dei test...
Come si comporta il tuo algoritmo con gli altri numeri? Se il tuo numero controlla solo alcuni numeri per un algoritmo generale sarà necessario selezionare quelli che il tuo algoritmo può controllare e quello che il tuo non può e se questo elimina il vantaggio rispetto ad usare solo un algoritmo più generale il tuo algoritmo diventa inutile dal punto di vista pratico (dal punto di vista teorico dipende da cosa c'è scritto nell'articolo e non ho dubbi che possa essere interessante). La stessa cosa succede se il tuo gruppo è molto più piccolo del totale dei semiprimi (nonché dei numeri composti).
Aggiungo inoltre che se il tuo algoritmo è nell'ordine delle 10K (e probabilmente 5000 sono già tante) linee di codice la convenienza ad implementarlo e a provare ad ottimizzarlo ulteriormente sono molto ridotte.
Ti spiego, brevemente, come funziona il tutto.
L'algoritmo è un sistema abbastanza complesso, un raggruppamento di casi.
Ogni caso è un insieme di semiprimi, legati tra loro, per una o più particolari caratteristiche.
La prima fase, velocemente crea una serie di valori, sulla base del semiprimo da trattare.
In base a questi valori, ricavati dal semiprimo, viene applicato l'algoritmo.
Nella prima fase, l'algoritmo si chiama QS-Zero, per il semplice fatto, che lavora ad un livello superficiale, in quanto tramite semplici operazioni di aritmetica modulare, si arriva direttamente alla scomposizione del numero, nei suoi fattori.
QS-Zero, ad oggi contiene 7 classi di semiprimi, ogni classe di semiprimi, è chiamata "Caso XXX". Questo perchè i semiprimi che appartengono a quella determinata classe, possono essere fattorizzati tutti, con la stessa procedura.
C'è ad esempio una classe di semiprimi, che viene fattorizzata tramite un semplice mod n, dove n è un valore ricavato dal semiprimo stesso, durante la prima fase quella di analisi, che è molto veloce.
QS-Zero, prova ad applicare i 7 metodi di scomposizione sul semiprimo da trattare, se falliscono, si passa ad un livello più complesso, dove il semiprimo, deve essere spostato, tramite una serie di elaborazioni, all'interno di un serie numerica. Deve quindi acquisire il semiprimo, particolari proprietà, che permettono a QSX, di elaborarlo e fattorizzarlo correttamente.
QSX è l'evoluzione, di QS-Zero. QSX lavora infatti a più livelli. Alcuni livelli sono molto brevi, per cui, la fattorizzazione stessa del semiprimo, una volta eseguito QS-Zero è abbastanza veloce. Altri semiprimi, hanno bisogno di essere spostati a livelli molto alti, per cui, prima di poter applicare QSX, ci vuole molto tempo.
Allo stato attuale, QSX può fattorizzare qualsiasi semiprimo, l'intera tabella di 200 milioni di semiprimi è stata fattorizzata da QSX, solo che per alcuni semiprimi, i tempi sono stati lunghi. Lavorando con semiprimi molto grandi, QSX, allo stato attuale, presenta dei tempi di elaborazione troppo alti.
Sto lavorando infatti per fare in modo che un semiprimo raggiunga il livello corretto per essere fattorizzato nel più breve tempo possibile e questa è la difficoltà attuale.
Questo sistema l'ho creato, combinando i vari numeri primi, studiando i loro prodotti (semiprimi) e delineando, via via, le varie proprietà che essi hanno.
Per cui, rispondendo alla tua domanda se conviene usare o meno questo algoritmo, ti rispondo: conviene applicarlo, poichè i tempi di fattorizzazione, tranne i casi in cui il livello del semiprimo, sia molto alto, sono molto veloci e in alcuni casi, se il semiprimo fa parte di una delle classi di QS-Zero, la scomposizione è eseguita nel giro di pochi secondi.
"avinerba":Vorrei porti io un problema... quanto ci metti a dire che il semiprimo è un semiprimo ed è dentro il gruppo che ti serve. Perché per farlo dovrai fare dei test...
Come si comporta il tuo algoritmo con gli altri numeri? Se il tuo numero controlla solo alcuni numeri per un algoritmo generale sarà necessario selezionare quelli che il tuo algoritmo può controllare e quello che il tuo non può e se questo elimina il vantaggio rispetto ad usare solo un algoritmo più generale il tuo algoritmo diventa inutile dal punto di vista pratico (dal punto di vista teorico dipende da cosa c'è scritto nell'articolo e non ho dubbi che possa essere interessante). La stessa cosa succede se il tuo gruppo è molto più piccolo del totale dei semiprimi (nonché dei numeri composti).
Aggiungo inoltre che se il tuo algoritmo è nell'ordine delle 10K (e probabilmente 5000 sono già tante) linee di codice la convenienza ad implementarlo e a provare ad ottimizzarlo ulteriormente sono molto ridotte.
Ti spiego, brevemente, come funziona il tutto.
L'algoritmo è un sistema abbastanza complesso, un raggruppamento di casi.
Ogni caso è un insieme di semiprimi, legati tra loro, per una o più particolari caratteristiche.
La prima fase, velocemente crea una serie di valori, sulla base del semiprimo da trattare.
In base a questi valori, ricavati dal semiprimo, viene applicato l'algoritmo.
Nella prima fase, l'algoritmo si chiama QS-Zero, per il semplice fatto, che lavora ad un livello superficiale, in quanto tramite semplici operazioni di aritmetica modulare, si arriva direttamente alla scomposizione del numero, nei suoi fattori.
QS-Zero, ad oggi contiene 7 classi di semiprimi, ogni classe di semiprimi, è chiamata "Caso XXX". Questo perchè i semiprimi che appartengono a quella determinata classe, possono essere fattorizzati tutti, con la stessa procedura.
C'è ad esempio una classe di semiprimi, che viene fattorizzata tramite un semplice mod n, dove n è un valore ricavato dal semiprimo stesso, durante la prima fase quella di analisi, che è molto veloce.
QS-Zero, prova ad applicare i 7 metodi di scomposizione sul semiprimo da trattare, se falliscono, si passa ad un livello più complesso, dove il semiprimo, deve essere spostato, tramite una serie di elaborazioni, all'interno di un serie numerica. Deve quindi acquisire il semiprimo, particolari proprietà, che permettono a QSX, di elaborarlo e fattorizzarlo correttamente.
QSX è l'evoluzione, di QS-Zero. QSX lavora infatti a più livelli. Alcuni livelli sono molto brevi, per cui, la fattorizzazione stessa del semiprimo, una volta eseguito QS-Zero è abbastanza veloce. Altri semiprimi, hanno bisogno di essere spostati a livelli molto alti, per cui, prima di poter applicare QSX, ci vuole molto tempo.
Allo stato attuale, QSX può fattorizzare qualsiasi semiprimo, l'intera tabella di 200 milioni di semiprimi è stata fattorizzata da QSX, solo che per alcuni semiprimi, i tempi sono stati lunghi. Lavorando con semiprimi molto grandi, QSX, allo stato attuale, presenta dei tempi di elaborazione troppo alti.
Sto lavorando infatti per fare in modo che un semiprimo raggiunga il livello corretto per essere fattorizzato nel più breve tempo possibile e questa è la difficoltà attuale.
Questo sistema l'ho creato, combinando i vari numeri primi, studiando i loro prodotti (semiprimi) e delineando, via via, le varie proprietà che essi hanno.
Per cui, rispondendo alla tua domanda se conviene usare o meno questo algoritmo, ti rispondo: conviene applicarlo, poichè i tempi di fattorizzazione, tranne i casi in cui il livello del semiprimo, sia molto alto, sono molto veloci e in alcuni casi, se il semiprimo fa parte di una delle classi di QS-Zero, la scomposizione è eseguita nel giro di pochi secondi.
Saluti,
Andrea Vinerba
Probabilmente la parte più interessante sarà la parte riguardante le classi di semiprimi. Le classi hanno caratteristiche che li accumulano oltre all'essere scomponibili usando lo stesso metodo? Lo dico solo perché potrebbe essere un quesito interessante (se già non hai fatto ricerche a riguardo).
Ritengo comunque che farne una propria implementazione non sia la cosa più fattibile del mondo...
Solo una domanda perché Maxima e non C++, C, fortran o Ada con qualche libreria sui grandi numeri come GMP o PARI e MYSQL? Se programmata bene potresti avere ulteriori accelerazioni ed è più facile trovare matematici che sanno usare questi linguaggi che quelli che usano maxima.
Probabilmente la parte più interessante sarà la parte riguardante le classi di semiprimi. Le classi hanno caratteristiche che li accumulano oltre all'essere scomponibili usando lo stesso metodo? Lo dico solo perché potrebbe essere un quesito interessante (se già non hai fatto ricerche a riguardo).
Ritengo comunque che farne una propria implementazione non sia la cosa più fattibile del mondo...
Solo una domanda perché Maxima e non C++, C, fortran o Ada con qualche libreria sui grandi numeri come GMP o PARI e MYSQL? Se programmata bene potresti avere ulteriori accelerazioni ed è più facile trovare matematici che sanno usare questi linguaggi che quelli che usano maxima.
Le classi di semiprimi godono di proprietà veramente uniche. Queste proprietà sono state delineate solo grazie ai valori di base che calcolo all'inizio quando viene esaminato il semiprimo. La parte più interessante è stata l'ultimo mese, quando sono passato ad analizzare i fattori che compongono il semiprimo e ho creato delle relazioni ben precise tra il prodotto e i due fattori. Per questo stò analizzando i primi 15 milioni di primi, per delineare meglio queste proprietà. Non solo. Nell'evoluzione di QSX, ho creato degli indicatori, o meglio sono riuscito a stabilire tramite i valori di base iniziali, come si comportano i fattori del semiprimo, riuscendo quindi a circoscrivere l'insieme dei valori del fattore più piccolo P, in modo tale da indirizzare meglio l'algoritmo durante la sua elaborazione.
Infine: stò analizzando delle tabelle generate dall'analisi del semiprimo, dove per alcuni semiprimi riesco ad individuare un semiprimo che io chiamo "il gemello" che non condivide nessun fattore con il primo ma presenta un comportamento identico, quando è sottoposto ad alcune operazioni mod n. In pratica, per questa classe di semiprimi, non si lavora sul semiprimo, ma sul gemello, che porta inevitabilmente alla scomposizione del fratello maggiore.
La cosa più interessante, per concludere, è l'analisi dei semiprimi adiacenti a quello che cerchi di fattorizzare. Proprio dalla loro analisi, riesco a circoscrivere il campo di azione, poichè ho individuato un andamento stabile del fattore più piccolo che cresce o diminuisce in base alla grandezza dei valori base degli altri semiprimi adiacenti.
Insomma, non mi sono proposto così, a mani vuote, ho eseguito veramente analisi complesse di intere serie numeriche e molte analisi le ho fatte a mano, per capire meglio il comportamento di alcune proprietà.
Ho usato Maxima, solo per abbreviare notevolmente lo sviluppo della ricerca, poichè con Maxima, posso compiere una serie di operazioni velocemente, essendo facile da usare il linguaggio di programmazione di questo software.
Adesso, spero di poter integrare nell'ultima release di QSX le ultime novità, tra l'altro ogni giorno riesco ad affinare meglio le varie tecniche e gli insiemi, le classi, stanno crescendo notevolmente rispetto a qualche mese fa. Riguardo ai livelli di QSX, sono riuscito per alcuni semiprimi, ad abbassare notevolmente il tempo di elaborazione.
La strada secondo me, è quella giusta e i risultati per il momento, mi danno fiducia.
Sono passati uasi 3 anni!
Che ne è della tua ricerca?
Che ne è della tua ricerca?
L'argomento è interessante, come mai questo up? Ci sono novità?
La mia domanda era rivolta ad Avinerba che, 3 anni fa, sembrava vicino ad una soluzione del problema, decisamente
interessante, della scomposizione dei numeri semiprimi!
interessante, della scomposizione dei numeri semiprimi!
Sono passati 10 anni! Novità sul tuo algoritmo sulla scomposizione dei numeri semiprimi?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo