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 6 2344 RRqR ( 0 < R 4 < R 3 ) ……………… .………….. finché non si giunge ad un resto nullo. Infatti le disuguaglianze precedenti mostrano che i successivi resti formano una successione decrescente di numeri positivi: b > R 1 > R 2 > R 3 >……> 0 Quindi, dopo al più b operazioni ( spesso molto meno, poiché la differenza tra due r successivi è, generalmente, maggiore di 1 ), deve apparire il resto 0: 21nnnn RRqR 1 10 nnn RRq Quando ciò accade si ha ( a,b ) = R n cioè, in altre parole, ( a,b ) è l’ ultimo resto positivo delle divisioni successive. Dall’algoritmo euclideo si può dedurre una proprietà molto importante del massimo comun divisore ( a,b ) di due numeri Corollario 2.1 Se d = ( a, b), si possono trovare due numeri interi, k e l, tali che dkalb . Si può inoltre dimostrare il seguente: Teorema 2.2 Se un primo divide il prodotto di due numeri, esso deve dividere (almeno) uno di essi. 3 CONGRUENZE 3.1 Definizione e prime proprietà Il concetto e la notazione di congruenza, dovuti a Gauss, servono a chiarire e a sem- plificare ogni ragionamento in cui si presenti il concetto di divisibilità dei numeri interi per un numero intero fissato m. Definizione 3.1 Siano a,b e m numeri interi con m > 0. Si dice che a è congruo b modulo m se m divide la differenza a-b. In tal caso scriveremo: a ≡ b ( mod m )

Anteprima della Tesi di Mirko Dal Pozzo

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

Tesi di Laurea

Facoltà: Ingegneria

Autore: Mirko Dal Pozzo Contatta »

Composta da 113 pagine.

 

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

 

Consultata integralmente 2 volte.

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