01/02/2008, 17:41
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)$.
02/02/2008, 14:18
avinerba ha scritto: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.
02/02/2008, 15:24
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.
02/02/2008, 16:21
avinerba ha scritto: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
02/02/2008, 16:54
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.
06/01/2011, 23:31
07/01/2011, 02:05
07/01/2011, 18:30
18/03/2019, 07:38
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.