numeri primi algoritmi

[raffa82]

Ciao ragazzi,
sono nuovo del sito ed ho una curiosità sulla primalità di un numero.
In realta quello che voglio sapere è:

Esiste un algoritmo che mi dice se un numero n è primo compiendo al più n passi,
e questi n passi sono operazioni elementari come addizione o sottrazione?

[Nonno Bassotto]

Sì, almeno per n grande. Di solito il numero di passi si misura con il numero di cifre di n, che è circa log n. È stato trovato non molto tempo fa un algoritmo di primalità (cioè che mi dice se un numero è primo o no) che impiega un numero di passi polinomiale nel numero di cifre. Questo significa che il numero di passi necessario è dell'ordine di p(log n), dove p è un certo polinomio. Questo è minore di n per n grande.

L'articolo che presenta l'algoritmo è qui
http://fatphil.org/maths/AKS/
http://en.wikipedia.org/wiki/AKS_primality_test

[raffa82]

ciao nonno,
grazie mille per la celere risposta,
tuttavia avrei una curiosità ulteriore che forse puoi torgliermi senza che io debba leggermi come funziona tutto l'algortmo.
Il numero di passi che compie,
che tipo di operazioni svolge?
Per indenderci usa per esempio moltiplicazioni, divisioni.....
che credo computazionalmente siano ben diversi da addizioni e sottrazioni.
Grazie mille per la tua disponibilità

[raffa82]

ma questo algoritmo mi può dire anche in caso il numero sia non primo,
per es se è prodotto di due num, quali sono questi due numeri?
o roba del genere.

[Ponnamperuma]

Se n è composito, dunque non primo, esiste un teorema che dice che n ha un fattore $ \leq \sqrt{n} $... Vero è che per n grande può essere difficoltoso calcolare la sua radice quadrata, ma comunque mi pare un risultato molto interessante!

[fph]

Il numero di passi che compie,
che tipo di operazioni svolge?
Per indenderci usa per esempio moltiplicazioni, divisioni.....
che credo computazionalmente siano ben diversi da addizioni e sottrazioni.

Un'addizione o una sottrazione impiegano un numero di passi proporzionale a log n. Una moltiplicazione o una divisione impiegano un numero di passi proporzionale a $ (\log n)^2 $, con l'algoritmo "in colonna", ma con algoritmi piu' sofisticati si scende a $ \log n \log \log n $ (per valori di n molto grandi).
Quindi il risultato enunciato da Nonno non cambia, il numero di operazioni è sempre un polinomio in log n, anche se il suo grado può aumentare.

ciao,

[raffa82]

ragazzi so che non è una domanda matematica,
ma voi forse ne saprete più di me sui misteri e i piaceri dei numeri primi.
La mia domanda è relegata alla fantasia.
Ma se uno creasse un algoritmo che in tempo polinomiale dicesse se un numero è primo o senno ne desse i numeri che lo compongono,
come farebbe a ricavarci soldi?
Io stavo pensando di decarmi a quello ma vorrei sapere se gli sforzi potrebbero essere ricompensati, o sarebbe puro tempo usato nel piacere della matematica

[SkZ]

crittografia!
moltissima crittografia si basa sulla difficolta' di scomporre in fattori primi numeri molto grandi.
http://it.wikipedia.org/wiki/RSA
Non so quanti soldi riusciresti a fare, ma ti arriverebbero molte maledizioni!

[raffa82]

conoscete qualche libreria in c++ per manipolare numeri molto molto grandi?
grazie mille, siete tutti molto gentili

[SkZ]

innanzitutto e' bene che ti prendi un computer ad almeno 64bit che permette gia di suo la gestione di numeri piu' grandi rispetto ai sistemi a 32bit
http://it.wikipedia.org/wiki/Long_integ ... eri_comuni
meglio ancora un cluster di workstation o in rack
http://en.wikipedia.org/wiki/19-inch_rack
http://www.e4company.com

dai un'occhiata (trovato scrufugliando con google )
http://www.gnu.org/software/gsl/
http://www.faginfamily.net/barry/Papers/JPDC92.htm
http://www-03.ibm.com/systems/p/software/essl.html

altro link su crittografia e numeri primi
http://it.wikipedia.org/wiki/Crittograf ... mentazione

[Nonno Bassotto]

ragazzi so che non è una domanda matematica,
ma voi forse ne saprete più di me sui misteri e i piaceri dei numeri primi.
La mia domanda è relegata alla fantasia.
Ma se uno creasse un algoritmo che in tempo polinomiale dicesse se un numero è primo o senno ne desse i numeri che lo compongono,
come farebbe a ricavarci soldi?
Io stavo pensando di decarmi a quello ma vorrei sapere se gli sforzi potrebbero essere ricompensati, o sarebbe puro tempo usato nel piacere della matematica

Credo che esista anche per fattorizzare in tempo polinomiale, il collo di bottiglia dovrebbe essere testare la primalità, ma non sono sicuro. Il fatto è che in tempo polinomiale non vuol dire efficiente, se i coefficienti sono grossi. Un algoritmo che ci metta 10000000000000000000000000000000000000000000000000*(numero di cifre)^2 anni a fattorizzare un numero ha pochi utilizzi pratici.

Quanto a farci i soldi, se tu scoprissi un algoritmo che fattorizza i numeri davvero velocemente, hai grosso modo le seguenti possibilità

1) L'algoritmo è più efficace di quelli attuali, ma non molto. Le banche raddoppiano il numero di cifre delle chiavi che usano e stanno al sicuro.
2) L'algoritmo è spaventosamente più efficace di quelli attuali, nel qual caso
2a) Pubblichi l'algoritmo su una rivista, dopo di che l'economia mondiale crolla.
2b) Ti tieni l'algoritmo per te e fai una montagna di soldi finché non ti beccano. Purtroppo potrebbe essere moooolto facile essere beccato interagendo in transazioni finanziarie.
2c) Annunci di avere l'algoritmo, ma dici che non lo pubblichi per evitare il caos. Il giorno dopo la NSA ti porta a Guantanamo.
2d) Vendi a un prezzo spaventoso l'algoritmo a qualche società di sicurezza, dopo di che i loro scagnozzi ti consegnano alla NSA...

Uhmmm... mica facile ricavarne veramente dei soldi!

[fph]

conoscete qualche libreria in c++ per manipolare numeri molto molto grandi?

Lo standard de facto dovrebbe essere la libreria GNU gmp. Ha anche un'interfaccia C++.

Comunque quello che stai pensando di fare non è per nulla un compito facile... auguri.

[SkZ]

un consiglio: non puntare tanto sulla potenza del tuo computer quanto su quella del tuo cervello. I principali istituti hanno accesso a calcolatori che ci possiamo solo sognare, quindi in questo caso affrontare il problema a "brute force" aiuta poco.
mi aggiungo agli 'in bocca al lupo' e sta attento ai numeri primi (io per colpa loro ci ho rimesso una ragazza )

Penso che potrebbe essere utile dare un'occhiata a "quanto c'e' in letteratura" sulla Congettura di Riemann sui numeri primi (ne so poco, fph&C di sicuro sapranno dirti di piu' e meglio) http://it.wikipedia.org/wiki/Congettura_di_Riemann

edit:
Lo so che postare tanti link non e' molto carino ma qui
http://matematica.uni-bocconi.it/indice ... iprimi.htm
ci sono vari articoli intetressanti sull'argomento che magari ti potrebbero aiutare

@fph: una idea si potrebbe aprire una sezione solo per i numeri primi

[raffa82]

ragazzi non mi pare vero,
siete grandissimi.
Grazie mille.
Ora ho però ancora qualche problema pratico da risolvere.
Ho scaricato la libreria GMP,
ma mi sta dando un sacco di fastidi,
qualcuno può aiutarmi?
Uso visual studio 2005 e non sono sicuro di saperlo configurare bene

[SkZ]

Mi stavo leggendo il sito delle gmp e nella sezione "Help:guest accounts needed" scrivono
"The systems need to run Unix (such as BSD or GNU/Linux). (People sometimes offer us accounts on Windows machines; unfortunately, that isn't useful since we don't develop GMP for such arcane platforms.)"

trovato altro: guarda qui
http://www.swox.com/gmp/manual/Notes-fo ... stems.html