Messaggioda avinerba » 01/02/2008, 18: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)$.


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
Starting Member
Starting Member
 
Messaggio: 13 di 15
Iscritto il: 16/07/2007, 12:12

Messaggioda vict85 » 02/02/2008, 15: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.


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.
vict85
Moderatore
Moderatore
 
Messaggio: 112 di 9887
Iscritto il: 16/01/2008, 01:13
Località: Berlin

Messaggioda avinerba » 02/02/2008, 16: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.


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.
Ultima modifica di avinerba il 14/01/2010, 09:34, modificato 1 volta in totale.
avinerba
Starting Member
Starting Member
 
Messaggio: 14 di 15
Iscritto il: 16/07/2007, 12:12

Messaggioda vict85 » 02/02/2008, 17: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


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.
vict85
Moderatore
Moderatore
 
Messaggio: 117 di 9887
Iscritto il: 16/01/2008, 01:13
Località: Berlin

Messaggioda avinerba » 02/02/2008, 17: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.


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.
avinerba
Starting Member
Starting Member
 
Messaggio: 15 di 15
Iscritto il: 16/07/2007, 12:12

Messaggioda mKop » 07/01/2011, 00:31

Sono passati uasi 3 anni!
Che ne è della tua ricerca?
mKop
Starting Member
Starting Member
 
Messaggio: 1 di 3
Iscritto il: 07/01/2011, 00:27

Messaggioda Rggb » 07/01/2011, 03:05

L'argomento è interessante, come mai questo up? Ci sono novità?
Avatar utente
Rggb
Advanced Member
Advanced Member
 
Messaggio: 1075 di 2202
Iscritto il: 30/07/2009, 18:27

Messaggioda mKop » 07/01/2011, 19:30

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!
mKop
Starting Member
Starting Member
 
Messaggio: 2 di 3
Iscritto il: 07/01/2011, 00:27

Re: Scomposizione in fattori di un semiprimo

Messaggioda mKop » 18/03/2019, 08:38

Sono passati 10 anni! Novità sul tuo algoritmo sulla scomposizione dei numeri semiprimi?
mKop
Starting Member
Starting Member
 
Messaggio: 3 di 3
Iscritto il: 07/01/2011, 00:27

Precedente

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

Chi c’è in linea

Visitano il forum: Nessuno e 9 ospiti