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 2 CAPITOLO 1 Fattorizzazione in numeri primi 1 I NUMERI PRIMI Nella teoria dei numeri è di fondamentale importanza la classe dei numeri primi. Definizione 1.1 Un numero primo è un numero intero, maggiore di 1, che non ammette divisori diversi da sé stesso e da 1. Definizione 1.2 Un numero che non sia né 1, né un primo è detto numero composto. Definizione 1.3 Un numero naturale d si dice divisore o fattore di un numero naturale n, se esiste un numero naturale c tale che ndc ; in tal caso scrive- remo d | n. L’importanza della classe dei numeri primi è dovuta al fatto che Proposizione 1.1 Ogni numero intero maggiore di 1 o è primo o è rappresen- tabile come prodotto di primi. Dimostrazione Per dimostrare tale asserzione applichiamo il metodo di induzione. La posizione è vera per n = 2, essendo 2 un primo. Assumiamo che la proposizione sia vera per tutti i numeri fino a n – 1 e mostria- mo che vale anche per n. Se n è primo, non dobbiamo provare nulla. Se n è composto, per definizione è rappresentabile come prodotto di due numeri, d 1 e d 2 , entrambi maggiore di uno e minori di n e per l’ipotesi induttiva, ognuno di essi o è primo o è rappresentabile come prodotto di primi. Sostituendo a d 1 e d 2 le rispettive espressioni come prodotti di primi otteniamo che anche n = d 1 * d 2 è un prodotto di primi, e quindi la proposizione è provata anche per n.

Anteprima della Tesi di Mirko Dal Pozzo

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

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.