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 3361 click dal 06/04/2005.

 

Consultata integralmente 2 volte.

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