Domanda sulla complessità computazionale
Se ho un algoritmo che calcola i P primi fino ad un numero N in [(2/3)*N]-P :
1) si può applicare il teorema dei numeri primi?
2) se si la 1) qual'è la complessità computazionale del algoritmo?
1) si può applicare il teorema dei numeri primi?
2) se si la 1) qual'è la complessità computazionale del algoritmo?
Risposte
Ciao
volevo farvi una domanda
Sia $RSA$ un numero prodotto di due primi $X$ ed $Y$ , $RSA=X*Y$
Per vedere se $RSA$ è un numero primo la sua complessità computazionale è
$O(6^(log((RSA-1)/6)/log 6))$
Per fattorizzare $RSA$ la sua complessità è
$O(6^(log((Y-X)/6)/log 6))$
Ora per vedere se è primo non conviene (me ne sono accorto)
ma per fattorizzare $RSA$ non so capirlo.
Mi dareste una spiegazione gentilmente.
Edit
ho spiegato l'algoritmo ed ho fatto un esempio.
ho ritoccato la complessità verso il basso
http://www.albericolepore.org/fattorizz ... di-lepore/
volevo farvi una domanda
Sia $RSA$ un numero prodotto di due primi $X$ ed $Y$ , $RSA=X*Y$
Per vedere se $RSA$ è un numero primo la sua complessità computazionale è
$O(6^(log((RSA-1)/6)/log 6))$
Per fattorizzare $RSA$ la sua complessità è
$O(6^(log((Y-X)/6)/log 6))$
Ora per vedere se è primo non conviene (me ne sono accorto)
ma per fattorizzare $RSA$ non so capirlo.
Mi dareste una spiegazione gentilmente.
Edit
ho spiegato l'algoritmo ed ho fatto un esempio.
ho ritoccato la complessità verso il basso
http://www.albericolepore.org/fattorizz ... di-lepore/
Ti ripeto un po' quello che ti ho gia' spiegato in un altro post. Forse le tue idee sono anche buone, ma le esponi in modo disordinato e (almeno per me) quasi incomprensibile.
Venendo alla matematica:
- che la fattorizzazione costi meno di un test di primalita' mi sembra assurdo: se so fattorizzare con un algoritmo economico, posso usare quello e automaticamente ho gratis anche un test di primalita'.
- nel link, a prescindere dalle notazioni poco chiare, non completi la spiegazione proprio nel momento piu' bello, quando avviene questa fantomatica divisione per $6$ che abbandonando l'anello degli interi magicamente dovrebbe fornire una fattorizzazione proprio nell'anello degli interi. Questo e' il principale elemento che mi manca per capire vagamente l'idea dell'algoritmo e . Ti prego di non rispondere a questa nota con una paginata di formule da sviluppare.
A titolo personale, penso che ti manchino solide basi di algebra per affrontare questi argomenti (nulla di male; mancano a qualcosa tipo il 99% della popolazione, me compreso), tanto che duri fatica anche solo ad esprimere le tue idee che, ripeto, possono anche avere qualcosa di buono ma risultano estremamente fumose e poco chiare.
Venendo alla matematica:
- che la fattorizzazione costi meno di un test di primalita' mi sembra assurdo: se so fattorizzare con un algoritmo economico, posso usare quello e automaticamente ho gratis anche un test di primalita'.
- nel link, a prescindere dalle notazioni poco chiare, non completi la spiegazione proprio nel momento piu' bello, quando avviene questa fantomatica divisione per $6$ che abbandonando l'anello degli interi magicamente dovrebbe fornire una fattorizzazione proprio nell'anello degli interi. Questo e' il principale elemento che mi manca per capire vagamente l'idea dell'algoritmo e . Ti prego di non rispondere a questa nota con una paginata di formule da sviluppare.
A titolo personale, penso che ti manchino solide basi di algebra per affrontare questi argomenti (nulla di male; mancano a qualcosa tipo il 99% della popolazione, me compreso), tanto che duri fatica anche solo ad esprimere le tue idee che, ripeto, possono anche avere qualcosa di buono ma risultano estremamente fumose e poco chiare.
Ne sono consapevole di avere carenze ma negli ultimi anni gli ultimi anni ho fatto lavori quali spazzino, custode, operaio. adesso sono disoccupato e mi diletto con queste cose
Eh sì, ma il suggerimento di Pappapero forse era nell'indirizzarti a costruirti queste basi e solo poi approfondire; in questo modo utilizzerai in modo più efficiente le energie che adesso probabilmente un po' sprechi ... 
Cordialmente, Alex
Cordialmente, Alex
grazie alex e pappappero ho intenzione di farlo
ma mi servirebbe imparare e prendere qualche soldino (perchè purtroppo non li ho) in cambio delle mie intuizioni
devo trovare qualcuno che creda nelle mie potenzialità e finanzi la mia formazione e le mie ricerche.
ma mi servirebbe imparare e prendere qualche soldino (perchè purtroppo non li ho) in cambio delle mie intuizioni
devo trovare qualcuno che creda nelle mie potenzialità e finanzi la mia formazione e le mie ricerche.
Te lo auguro sinceramente ma sappi che non sei l'unico ... 
ciao qualcuno mi potrebbe aiutare
ho una domanda sulla complessità computazionale:
L'alfabeto 25 lettere devo trovare un unica parola scelta da un altra persona tra tutte le parole di al massimo 625 lettere cioè comprese tra una parola da una lettera ad una parola da 625 lettere (ammettendo che esista)
quindi si parte da una complessità di n fino ad arrivare ad una complessità di ?
In che classe di complessità si trova questo problema?
ho una domanda sulla complessità computazionale:
L'alfabeto 25 lettere devo trovare un unica parola scelta da un altra persona tra tutte le parole di al massimo 625 lettere cioè comprese tra una parola da una lettera ad una parola da 625 lettere (ammettendo che esista)
quindi si parte da una complessità di n fino ad arrivare ad una complessità di ?
In che classe di complessità si trova questo problema?
Se non sbaglio arriva ad una complessità $\sum_{k=1}^(N^2) k!$ poichè $\sum_{k=1}^(625) k!$
e quindi si trova nella classe $NP-C$ per $K>=N$
Dico bene? Vi prego correggetemi se sbaglio
e quindi si trova nella classe $NP-C$ per $K>=N$
Dico bene? Vi prego correggetemi se sbaglio
Io non ho capito il problema, ne' quello che chiedi sul problema.
Scegliere una parola di 625 lettere in un alfabeto a 25 caratteri vuol dire scegliere un elemento qualsiasi in un insieme di $25^{625}$ elementi. Se io scelgo questa parola e ti dico di eliminarla l'unico algoritmo possibile e' provare tutte le parole fino a trovarla.
Scegliere una parola di 625 lettere in un alfabeto a 25 caratteri vuol dire scegliere un elemento qualsiasi in un insieme di $25^{625}$ elementi. Se io scelgo questa parola e ti dico di eliminarla l'unico algoritmo possibile e' provare tutte le parole fino a trovarla.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo