Abbiamo parlato delle sorgenti di casualita’ e come disponibilita’ di device. Oggi ne facciamo subito un utilizzo parlando di algoritmi probabilistici. Questi sono una vastissima classe di algoritmi che usano la probabilita’. Nel caso della crittografia la prob e’ fondamentale per non rendere prevedibile il comportamento di chi deve utilizzare protocolli difensivi per chi attacca. L’utilizzo principale della casualita’ e’ nella generazione delle chiavi: numeri primi molto grandi o con determinate caratteristiche.

Il nostro modello di calcolo, quello sui bit si estende immaginando diavere a disposizione questa sorgente di bit casuali che non deve essere sprecata in alcune modo e nelle analisi facciamo anche una stima rispetto all’entropia usata dal sistema.

Algoritmi Probabilistici

Algoritmo Montecarlo

Ecco un esempio di un algoritmo che approssima pigreco andando a sfruttare la casualita’:

Strategia montecarlo e’ quella di generare tanti punti e la frazione dovrebbe approssimare il pi greco. Tutti quelli che vedremo noi saranno tutti di tipo decisionale, uno che ha due possibili risposte: vero o falso.

L’indeterminazione proabibilistica potrebbe risiedere nella correttezza del risultato oppure nel tempo di calcolo. Vedremo quindi algoritmi Montecarlo e algoritmi Las Vegas, il primo e’ decisionale che sbaglia sulla risposta con una certa probabilita’ mentre las vegas risponde sempre giusto ma potrebbe non terminare mai.

Un algoritmo decisionale potrebbe essere visto anche come classificatore binario → algoritmo che decide se una mail sia spam e meno per esempio. Diamo una definizione precisa di montecarlo e che caratteristiche deve avere:

1. Su input la cui risposta esatta e’ true, restituisce true con una probabilita’ fissa epsiolon > 0. La cosa fondamentale e’ che sia un valore costante e indipendente dall’input.
2. Se invece la risposta esatta e’ false, questa deve essere sempre corretta.

Probability bounded one sided error Monte Carlo, questo sarebbe praticamente la definzione corretta. Questo descrive perfettamente che cosa stiamo osservando.

Vediamo un esempio di one sided error ma non e’ probability bounded. Per decidere se un numero e’ composto oppure primo. Pensiamo ad un algoritmo per decidere se un numero dispari e’ composto o meno:

Che caratteristiche ha questo algoritmo? Se il numero e’ composto potrebbe anche sbagliare. Se invece il numero e’ primo, dice che probabilmente e’ primo. Quando l’algoritmo dice composto ha sempre ragione, quando dice primo potrebbe sbagliare, mentre l’input e’ speculare. Quindi abbiamo one sided error, ma non e’ probability bounded.

Quindi praticamente una probabilita’ che porta a zero quando sceglio un dispari che questo sia un divisore. Qui praticamente e’ come se non avessi un bias, una fortuna, letteralmente niente che possa aiutarmi diciamo, nella ricerca di numeri primi.

In un algoritmo probabilistico la risposta dipende dalle scelte casuali che fa un algoritmo.

Se il numero e’ primo ci azzecca subito, data la formula sopra, se il numero e’ composto, lui potrebbe dirmi primo che non e’ piu’ di 99. Ci chiediamo come questa probabilita’ scenda a mano a mano che facciamo delle run.