Lezione del 23 maggio 2011 Crittografia.
Testo completo
Documenti correlati
Come per il problema della fattorizzazione in primi, anche per tale problema del logaritmo discreto non esiste a tutt’oggi un algoritmo di complessità polinomiale che, fissato il
[r]
Il sistema di Cesare è poco sicuro: l’intruso che intercetti il messaggio cifrato, potrebbe cercare di risalire al messaggio in chiaro con il metodo della “forza bruta”, provando
Alcuni argomenti trattati nel corso saranno i seguenti: studio della Teoria dei Numeri (soprattutto l’aritmetica dei numeri interi e in particolare dei numeri naturali, cioè
[r]
Negli algoritmi efficienti , al crescere della lunghezza x dell’input, il tempo di esecuzione cresce molto meno velocemente che negli altri algoritmi: tuttavia è utile osservare
Per esempio, per quanto detto in precedenza, esiste un algoritmo che calcola la divisione (con quoziente e resto) di 2 numeri naturali, e che ha complessità ≤ O(x t ) dove t =log
Dimostreremo ora che, dati 2 numeri naturali a,b con a>b, il numero n di divisioni effettuate nell’algoritmo Euclideo è log a (parte intera del logaritmo di a