Secondo requisito Diffie-Hellman

Secondo requisito: generazione di primo
...

Un metodo diretto per il calcolo di grandi numeri primi è il seguente:

genera M di k bit a caso // viene generato un numero di M di k bit (casuale)
for(i = 2; i * i <= M; i++){
	if(M % i == 0)
		goto 1 // al passo 1: "genera M di k bit a caso", M non è primo
}

return M // M è primo
C

Dopo che viene generato il numero , si controlla se è primo, se non lo è ne viene generato un altro, altrimenti, viene ritornato il numero primo che è stato generato.
Se è primo viene controllato verificando che la divisione tra e tutti i divisori che vanno da
a non diano come resto della divisione.

Come mai il ciclo si ferma proprio a

Il ciclo si ferma quando la , che nel ciclo avanza di un numero alla volta, moltiplicata per sé stessa restituisce un numero maggiore di . Se , vuol dire che è la radice di quadrata di . Quindi possiamo dire che il ciclo si finisce quando .

Altra domanda potrebbe essere, come mai non vengono controllati tutti i divisori fino a stesso? Il motivo è che esiste una regola della matematica che afferma che se un certo numero è non primo, esso avrà un divisore che è minore della radice quadrata di tale numero.

É facile che un numero sia primo?
...

Secondo il teorema di Euclide esistono infiniti numeri primi.

Teorema: esistono infiniti numeri primi

Dimostrazione:
la dimostrazione procede per assurdo.
Per assurdo diciamo che i numeri primi sono finiti:

risulta essere l'ultimo numero primo noto.

è il prodotto dei primi n numeri primi:

Ognuno dei fattori di questa moltiplicazione dividono .

CASO 1
Se considero il numero , tale numero diviso per o diviso per un numero (ovvero, i numeri che partecipano al prodotto per formare ) danno come resto della divisione 1. Il che vuol dire che è stato trovato un altro numero primo maggiore di .

CASO 2
Esiste un'altra possibilità: non è primo. Come abbiamo detto prima tutti i numeri non dividono . Quindi deve esistere un altro numero primo, che non appartiene all'insieme . Questo vuol dire che c'è un numero primo più grande di che divide , anche in questo caso non sarebbe l'ultimo numero primo.

Teorema dei numeri primi: un metodo per contare il numero di numeri primi

Sia il numero di numeri primi minori dell'intero .
Allora: Ovvero:

Ad esempio:

É facile che un numero di 100 cifre sia primo?
...

Nella crittografia, vengono utilizzati numeri primi molto grandi, anche con 100 cifre decimali.
I numeri primi di 100 cifre sono circa:

Osservazione

Come mai abbiamo fatto la differenza tra il numero di numeri primi con 100 cifre, meno il numero di numeri primi con 99 cifre? Il motivo è che siamo interessati a contare il numero di primi che ci sono solo con 100 cifre. Per cui, abbiamo sottratto a tale risultato il numero di primi che ci sono con 99 cifre.

Come possiamo vedere, il numero di numeri primi che ci sono con 100 cifre sono ovvero quasi . Ci sarà in media un numero primo ogni: è il numero di tentativi, in media, necessari per trovare un numero primo.
Questa frequenza può essere abbassata ancora di più sfruttando alcuni accorgimenti, tra cui:

escludere i numeri pari;
escludere i numeri multipli di 3 e di 5;

Generazione di (grandi) numeri primi
...

genera M di k bit a caso // viene generato un numero di M di k bit (casuale)
for(i = 2; i * i <= M; i++){
	if(M % i == 0)
		goto 1 // al passo 1: "genera M di k bit a caso", M non è primo
}

return M // M è primo
C

Riprendiamo l'algoritmo precedente, per generare un numero primo di 100 cifre potrebbero essere necessari un centinaio di tentativi.

L'algoritmo in questione è molto lento.
Anzitutto viene generato un numero di bit (ovvero di cento cifre binarie).
Il ciclo for parte da 2 fino ad arrivare alla radice quadrata di . Infatti il controllo che viene fatto è , ovvero , che vuol dire , in altre parole quando il prodotto di con sé stessa restituisce un numero maggiore di , si deve uscire dal ciclo.
Notiamo che incrementa di uno.
Il che vuol dire che avanza di un numero alla volta, fino a che il quadrato di non supera .
Questo vuol dire che se il numero non è primo vengono eseguiti tantissimi confronti.
Vengono eseguiti confronti, se è un numero con cifre, la sua radice quadrata avrà circa cifre.

Metodo probabilistico per la generazione di (grandi) numeri primi (I)
...

genera M di k bit a caso // viene generato un numero di M di k bit (casuale)
for(i = 0; i < T; i++){ // si ripete T volte
	genera a < M a caso
	if(test(a, M)) // test(a, M) controlla che il numero a non sia divisore di M
		goto 1 // al passo 1: "genera M di k bit a caso", M non è primo
}

return M // P(M non primo) < 2^(-T)
		 // P(M primo) > 1 - 2^(-T)
C

Con questo algoritmo la probabilità che sia primo è: mentre la probabilità che non lo sia è: La probabilità che sia primo è molto alta.

Esempio:
...

Supponiamo che , applichiamo la formula:

Test di primalità di Miller-Rabin
...

Il test di primalità di Miller-Rabin può dare dei falsi positivi, infatti la probabilità che non sia primo e che il test di Miller-Rabin dichiari che sia primo è inferiore a , La probabilità è abbastanza bassa. Tale probabilità può ancora abbassarsi.

Tale test si basa su due teoremi:

Piccolo teorema di Fermat (che sarà dimostrato in seguito): se è primo e , allora .
Conseguenza del principio fondamentale (che vediamo di seguito): se è primo e , allora o

Principio fondamentale
...

Se esistono e , tali che e , allora non è primo.

Dimostrazione
Sia , ci sono due casi:

se , allora , quindi
sia , sappiamo che , quindi .
La proprietà appena utilizzata si chiama identità di Eulero per i quadrati, tale proprietà afferma che se il , allora . Poi questa è una differenza di quadrati e può essere scomposta in .
Se il , sicuramente non può dividere , quindi deve per forza poter dividere , ciò contraddice , per cui . (Questa è anche la proprietà II che abbiamo visto all'inizio di questa argomentazione).

Siccome è diverso da e da , allora esiste un divisore di diverso da e da , questo vuol dire che non è primo.

Cosa vuol dire questa definizione?

Presi due numeri che sono congruenti in modulo con , quando elevati al quadrato, e che non sono sono congruenti in modulo , quando invece non sono elevati al quadrato, allora non è primo. Prendiamo per esempio e . , i numeri elevati al quadrato son congruenti in modulo con , ma rispettano la seconda parte del teorema? Si. Infatti , quindi è primo. Al contrario se non fosse stata rispettata questa seconda parte del teorema, allora non era un numero primo.

Conseguenza del principio fondamentale
...

Conseguenza del principio fondamentale è che se è primo ed esiste un numero che elevato al quadrato e messo in modulo con restituisce , ovvero , allora oppure .

Esempio: prendiamo come numero primo . Cerchiamo quali numeri restituiscono in modulo , il numero .

Metodo probabilistico per la generazione di grandi numeri primi (II)
...

genera M di k bit a caso // viene generato un numero di M di k bit (casuale)
for(i = 0; i < T; i++){ // si ripete T volte
	genera a < M a caso
	if(test(a, M)) // test(a, M) controlla che il numero a non sia divisore di M
		goto 1 // al passo 1: "genera M di k bit a caso", M non è primo
}

return M // P(M non primo) < 2^(-T)
		 // P(M primo) > 1 - 2^(-T)
C

Questa versione non cambia per niente, rispetto alla prima versione dell'algoritmo, se non fosse che il test(a, M) che viene eseguito è il test di Miller-Rabin.

Esempio con il test di Miller-Rabin:
Probabilità che un numero sia primo con il test di Miller-Rabin: Per : Che è un ottimo risultato.

Test di Miller-Rabin (`codice`)
...

d = 1;
for(i = k; i >= 0; i--){ // i parte dalla cifra più significativa
	x = d;
	d = (d * d) % M; // d = x^2 (mod M)

	if(d == 1 && x != 1 && x != M - 1)
		return true; // 1 = x^2 (mod M) ---(1)---

	if(b^i == 1)
		d = (d * a) % M;
		// d = a^(M - 1) mod M = 1      ---(2)---
}

if(d != 1)
	return true;
else
	return false;
C

Osservazioni sul codice

(1): Si tratta del teorema: se è primo e allora oppure
(2): Si tratta del piccolo teorema di Fermat: se è primo e , allora

Risultati utili per Diffie-Hellman (e per RSA)
...

Proprietà III

Se e sono relativamente primi, allora , possiamo dividere per lo stesso valore , ottenendo .

La dimostrazione di questa proprietà verrà affrontata alla fine della trattazione del cifrario RSA.

Teorema di Eulero

Se e sono relativamente primi, allora Ad esempio, consideriamo e , i due numeri sono relativamente primi (sono primi tra di loro, anche detti co-primi). Per testare il teorema abbiamo bisogno di calcolare anche la . Eulero afferma che , infatti .

Ricordiamo la definizione della funzione di Eulero: è il numero di interi minori di che sono relativamente primi con , ovvero gli elementi della funzione di Eulero, sono i numeri minori di , che hanno solo come massimo divisore comune con .

Dimostrazione:
Sia l'insieme dei numeri minori di M relativamente primi con . Ogni elemento dentro l'insieme è un numero intero positivo unico minore di e per ogni .
Sia, invece

L'insieme è una permutazione di : ovvero contiene gli stessi elementi di , possibilmente ordinati in modo diverso e questo è vero per due motivi:

è relativamente primo con e è relativamente primo con , quindi anche deve essererelativamente primo con . Questo vuol dire che tutti gli elementi di , sono numeri interi minori di , relativamente primi con .
In non ci sono valori duplicati. Supponiamo per assurdo che ci fossero due valori duplicati e , per la proprietà III: allora , ma dato che anche e sono relativamente primi con , questo vuol dire che i due numeri devono essere uguali, e questo non è possibile.

A questo punto: Mettiamo a fattor comune, al secondo membro, l'operazione
Mettiamo a fattor comune, al secondo membro, il termine che si ripete esattamente volte, quindi possiamo elevarlo proprio a :

Riscrivendo tutto:

Ora, per la proprietà III, dato che è relativamente primocon , possiamo semplificare: ottenendo:
=

Se due numeri x, y sono relativamente primi con n, allora anche il loro prodotto è relativamente primo con n

Corollario Piccolo teorema di Fermat: se è primo e , .

Secondo requisito: generazione di primo...

É facile che un numero sia primo?...

É facile che un numero di 100 cifre sia primo?...

Generazione di (grandi) numeri primi...

Metodo probabilistico per la generazione di (grandi) numeri primi (I)...

Esempio:...

Test di primalità di Miller-Rabin...

Principio fondamentale...

Conseguenza del principio fondamentale...

Metodo probabilistico per la generazione di grandi numeri primi (II)...

Test di Miller-Rabin (codice)...

Risultati utili per Diffie-Hellman (e per RSA)...