PDA

Visualizza versione completa : Complessità di algoritmi: numeri primi



grifis
04-04-2003, 17.11.32
Vi espongo il problema: voglio scrivere un programma in c++ che mi riferisca, dato un numero, se questo è primo o meno. Ho scritto l'algoritmo più banale che mi è venuto in mente, ma facendo un po' di calcoli sulla sua complessità, ho scoperto che questa cresce in modo esponenziale, e ciò non è un bene, dato che l'algoritmo risulta lento e, quindi, inadeguato. In pratica l'algoritmo divide il numero dato (n) per tutti i suoi minori compresi tra 2 e n/2 e controlla se per ogni divisione il resto è zero. Se trova una sola divisione il cui resto è zero, allora il numero non è primo, altrimenti lo è.

Quindi l'algoritmo fà n/2 divisioni con resto. Siccome il tempo impiegato per fare una divisione con resto è L^2 (con L=logn=numero delle cifre da cui è composto il numero), il tempo impiegato per fare n/2 divisioni con resto è n/2*(logn)^2, cioè (logn)^(2*n/2), cioè L^n, che è una funzione esponenziale e quindi lenta.

Arriviamo alla domanda: sapreste modificare l'algoritmo in modo che la sua complessità di calcolo sia polinomiale, o comunque minore di L^n?

follettomalefico
04-04-2003, 18.25.05
Uhm... questo link più esserti utile?
http://www.gimps.it/mersenne/prime-it.htm

:)

grifis
05-04-2003, 01.13.03
Originally posted by follettomalefico
Uhm... questo link più esserti utile?
http://www.gimps.it/mersenne/prime-it.htm

:)

Sì, grazie.

Socrates
05-04-2003, 03.53.29
Una buona parte degl'algoritmi di crittaggio attuale si fondano sul presupposto che l'integralita' dei numeri primi sia incalcolabile.
Recentemente ho sentito dire che qualcuno avrebbe trovato la formula per calcolare tutti i numeri primi.
Se cio' fosse vero, cedo a voi il piacere d'immaginarne tutte le conseguenze.

Dubito che il tuo algoritmo possa calcolare tutti i numeri primi da 1 a +infinto... E, inevitabilmente, la natura esponenziale del problema e' difficilmente contornabile.
Consiglio stronzo: se per il tuo compito devi essere in grado di calcolare rapidamente i numeri primi tra 0 e x, precalcolali in un array... A volte controllano talmente bene da non accorgersene...

Jinhio
05-04-2003, 09.56.05
Originally posted by Socrates
Una buona parte degl'algoritmi di crittaggio attuale si fondano sul presupposto che l'integralita' dei numeri primi sia incalcolabile.
Recentemente ho sentito dire che qualcuno avrebbe trovato la formula per calcolare tutti i numeri primi.
Se cio' fosse vero, cedo a voi il piacere d'immaginarne tutte le conseguenze.

Dubito che il tuo algoritmo possa calcolare tutti i numeri primi da 1 a +infinto... E, inevitabilmente, la natura esponenziale del problema e' difficilmente contornabile.
Consiglio stronzo: se per il tuo compito devi essere in grado di calcolare rapidamente i numeri primi tra 0 e x, precalcolali in un array... A volte controllano talmente bene da non accorgersene...

quoto
il funzionamento della crittografia a base pubblica si basa proprio sulla fattorizzazione dei numeri primi o sui loro logaritmi

che devi fare, tentare di craccare l'RSA o il DSA?

se è quello che ti interessa ti posso dare dei link che ti spegano il loro funzionamento;)

p.s. i numeri primi, pio, sono tantini, dato M >>1 i numeri primi tra 0 e M sono circa M/log(m)
prova con un numero nellordine di 10^10 e cvedrai quanti sono

grifis
05-04-2003, 11.44.48
Originally posted by Socrates

Dubito che il tuo algoritmo possa calcolare tutti i numeri primi da 1 a +infinto... E, inevitabilmente, la natura esponenziale del problema e' difficilmente contornabile.



Credo sia quasi impossibile realizzare un algoritmo capace di calcolare tutti i numeri primi, soprattutto perché non esiste (o ancora non è stata trovata) una relazione ben precisa che lega questi numeri, anche se poi ci sono dei casi speciali come i numeri di Mersenne. Si è riusciti solo a calcolarne la densità (come riportato da Jinhio).

Comunque io non pretendevo di costruire un algoritmo in grado di calcolare tutti i primi, né tantomeno che riuscisse a scomporre in fattori un numero composto da un numero di cifre elevato (e, in quel caso, il sistema RSA sarebbe fottuto), bensì di costruirne uno che, dato un numero, mi indicasse se questo fosse primo o meno, un problema di ben più semplice risoluzione. Purtroppo, visitando le pagine del sito indicatomi da folletto, ho scoperto che solo recentemente tre ricercatori hanno scoperto un algoritmo polinomiale in grado di calcolare la primalità di un numero, quindi mi pare abbastanza improbabile che io riesca a fare di meglio! Be', mi terrò il mio programma bràdipo.