Utilità dei numeri primi in informatica?
Ciao ragazzi. Mi sapete indicare l'utilità dei numeri primi in informatica, oltre alla crittografia?
Risposte
ciao,
bhe le proprietà intrinseche dei numeri primi sono usati in vari rami delle scienze. Queste proprietà ad esempio sono comode nel calcolo delle funzioni hashing.
Se si usa il resto della divisione di un numero con un numero primo, questo resto ha una probabilità di incidenza con un altro numero di partenza (la funzione hash è iniettiva) molto bassa, cioè ha una distribuzione di probabilità uniforme? (non ricordo bene qual'è la distribuzione esatta), cmq ha probabilità di collesioni non nulle, ma basse. Queste basse collisioni sono usate per creare strutture dati tipo i dizionari, nei database,...
si le funzioni hash sono sicuramente i più diffusi, perchè queste funzioni sono usate in una miriadi di algoritmi. Pure la crittografia usa funzioni hash, poi string matching, e mille cose. Ciao
bhe le proprietà intrinseche dei numeri primi sono usati in vari rami delle scienze. Queste proprietà ad esempio sono comode nel calcolo delle funzioni hashing.
Se si usa il resto della divisione di un numero con un numero primo, questo resto ha una probabilità di incidenza con un altro numero di partenza (la funzione hash è iniettiva) molto bassa, cioè ha una distribuzione di probabilità uniforme? (non ricordo bene qual'è la distribuzione esatta), cmq ha probabilità di collesioni non nulle, ma basse. Queste basse collisioni sono usate per creare strutture dati tipo i dizionari, nei database,...
si le funzioni hash sono sicuramente i più diffusi, perchè queste funzioni sono usate in una miriadi di algoritmi. Pure la crittografia usa funzioni hash, poi string matching, e mille cose. Ciao
Da qualche parte ho sentito dire che un problema dei processi di criptazione è che non si conosce un algoritmo per calcolare i numeri primi, che consentirebbe di fare sistemi inattaccabili o quasi; quindi direi che i numeri primi sono utilissimi nel campo della cifratura; altro non so ma mi piacerebbe approfondire.
"Giant_Rick":
Da qualche parte ho sentito dire che un problema dei processi di criptazione è che non si conosce un algoritmo per calcolare i numeri primi, che consentirebbe di fare sistemi inattaccabili o quasi; quindi direi che i numeri primi sono utilissimi nel campo della cifratura; altro non so ma mi piacerebbe approfondire.
Ni, quello che dici è per $1/4$ vero.
Per la crittografia RSA: non si conosce (ancora) un algoritmo che calcola in tempo umano la scomposizione di un numero in due fattori primi. Il numero è la chiave privata (lasciando da parte chiave pubblica), composta da due numeri primi moltiplicati assieme. Se la moltiplicazione è banale, la scomposizione in fattori è difficile. Da sottolineare che questi due numeri sono molto grandi, tipo 2048 bit. Se si usasse un computer quantistico questo sarebbe un giochetto da trovare (ma qua è fanta-informatica ancora).
Però si conoscono algoritmi che cercano numeri primi, non in tempo polinomiale. Mi sembra che ci sia un algoritmo appossimato che lo faccia e che usi la probabilità di errore, non ricordo bene.
"ham_burst":
[quote="Giant_Rick"]Da qualche parte ho sentito dire che un problema dei processi di criptazione è che non si conosce un algoritmo per calcolare i numeri primi, che consentirebbe di fare sistemi inattaccabili o quasi; quindi direi che i numeri primi sono utilissimi nel campo della cifratura; altro non so ma mi piacerebbe approfondire.
Ni, quello che dici è per $1/4$ vero.
[/quote]
Abbiamo trasmesso: ''Come cercare di sembrare minimamente informato e fare una gran brutta figura''.
A risentirci sule frequenze di giant_rickTV
"ham_burst":
Il numero è la chiave privata (lasciando da parte chiave pubblica), composta da due numeri primi moltiplicati assieme.
Forse intendevi il contrario: il numero, risultato del prodotto di due numeri primi, è nella chiave pubblica; la chiave privata è per l'appunto composta (anche) dai fattori primi del numero stesso.
"ham_burst":
Però si conoscono algoritmi che cercano numeri primi, non in tempo polinomiale. Mi sembra che ci sia un algoritmo appossimato che lo faccia e che usi la probabilità di errore, non ricordo bene.
Meglio ancora, sono noti algoritmi molto veloci di test della primalità, usati proprio nella generazione di numeri primi grandi.
Con chiavi RSA abbastanza lunghe, attualmente considerate intrinsecamente sicure, è necessario usare numeri di centinaia di cifre decimali. Per fare questo basta (si fa per dire) generare molti numeri grandi e verificare se sono primi.
"Rggb":Però si conoscono algoritmi che cercano numeri primi, non in tempo polinomiale. Mi sembra che ci sia un algoritmo appossimato che lo faccia e che usi la probabilità di errore, non ricordo bene.
Meglio ancora, sono noti algoritmi molto veloci di test della primalità, usati proprio nella generazione di numeri primi grandi.
Con chiavi RSA abbastanza lunghe, attualmente considerate intrinsecamente sicure, è necessario usare numeri di centinaia di cifre decimali. Per fare questo basta (si fa per dire) generare molti numeri grandi e verificare se sono primi.
Sono andato a recuperarmi il libro dove avevo letto di questo algoritmo, ce ne erano vari uno con complessita $O(sqrt(n))$ però che non è polinomiale alla dimensione del problema.
Quello che citavo che usava la probabilità di errore ha complessità $O(logn)$ che sono il numero di operazioni aritmetiche, che mi sembra essere quello scopero da Rivest, anche quello che citi te ha questa complessità? ma meglio di così non so se si possa fare, ma non si sa mai.
Invece il problema contrario (che ovviamente ricordavo male per la chiave RSA), non si sa ne se è risolvibile in tempo polinomiale ne se è un problema difficile....
"ham_burst":
Quello che citavo che usava la probabilità di errore ha complessità $O(logn)$ che sono il numero di operazioni aritmetiche, che mi sembra essere quello scopero da Rivest, anche quello che citi te ha questa complessità? ma meglio di così non so se si possa fare, ma non si sa mai.
Una breve sintesi dello stato dell'arte la trovi su http://primes.utm.edu/prove/index.html
Dopo puoi passare ad approfondire. Enjoy!
Di algoritmo deterministico per la primalità che lavora in tempo polinomiale ce n'è solo uno (che io sappia) ed è l'AKS. O almeno è l'unico di cui è stata provata la complessità polinomiale nel caso peggiore.
Tuttavia ha complessità troppo elevata ($O(n^12)$ dove n è la lunghezza dell'input) per venire utilizzato (anche se è stato poi ottimizzato). Normalmente si usano degli algoritmi probabilistici (che quindi contemplano una soglia d'errore che può essere resa piccola a piacere a patto di reiterare il test) come il Miller-Rabin oppure algoritmi come l'ECPP di cui non conosciamo la complessità esatta.
In realtà esistono anche altri algoritmi deterministici polinomiali, ma si basano su congetture non provate.
Tuttavia ha complessità troppo elevata ($O(n^12)$ dove n è la lunghezza dell'input) per venire utilizzato (anche se è stato poi ottimizzato). Normalmente si usano degli algoritmi probabilistici (che quindi contemplano una soglia d'errore che può essere resa piccola a piacere a patto di reiterare il test) come il Miller-Rabin oppure algoritmi come l'ECPP di cui non conosciamo la complessità esatta.
In realtà esistono anche altri algoritmi deterministici polinomiali, ma si basano su congetture non provate.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo