Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Il test di primalità di Miller-Rabin e il metodo crittografico di ElGamal

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

CAPITOLO 1: prerequisiti teorici 11 Teorema 5.2 Supponiamo che ( a,m ) = d. Allora la condizione necessaria e suffi- ciente affinché la congruenza lineare (mod )axb m { abbia soluzione è che d | b. Se ciò accade la congruenza ha esattamente d soluzioni distinte, cioè tra loro incongrue modulo m. Osservazione: Se d | b, risolvere la congruenza lineare (mod )axb m { equivale a risolvere la congruenza lineare (mod ) ab m x dd { , nel senso che l’insieme dei numeri che soddisfano la prima congruenza coincide con l’insieme dei numeri che soddisfano la seconda. Infatti, se x 0 risolve la prima congruenza, per qualche intero k si ha che 0 ax bmk e dividendo ambo i membri per d troviamo che 0 abm x k ddd ovvero x 0 risolve la seconda congruenza. Viceversa, se x 0 risolve la seconda congruenza, per qualche intero h si ha che 0 abm x h ddd e moltiplicando ambo i membri per d troviamo che 0 x bmh ovvero x 0 risolve la prima congruenza. Dimostrazione Proviamo che se la congruenza lineare (mod )axb m { ha soluzione, allora d | b. Sia x 0 una soluzione della congruenza lineare; allora per qualche intero k si ha che: 0 ax bmk da cui 0 bax mk Ora essendo d = ( a,m ), d | a e d | m, ossia adz e mdw con ,zw Z . Possiamo allora raccogliere il fattore d a secondo membro, ottenendo che 0 ()bd zx wk Ma ciò vale ad affermare che d | b. Supponiamo ora che d | b. Per l’osservazione fatta preliminarmente sappiamo che risolvere la congruenza lineare (mod )axb m { equivale a risolvere la congruenza lineare (mod ) ab m x dd { .Consideriamo allora la seconda congruenza.

Anteprima della Tesi di Mirko Dal Pozzo

Anteprima della tesi: Il test di primalità di Miller-Rabin e il metodo crittografico di ElGamal, Pagina 11

Tesi di Laurea

Facoltà: Ingegneria

Autore: Mirko Dal Pozzo Contatta »

Composta da 113 pagine.

 

Questa tesi ha raggiunto 3353 click dal 06/04/2005.

 

Consultata integralmente 2 volte.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.