Heap Sort. L’algoritmo heap sort è il più lento di quelli di ordinamento
O(n * log n) ma, a differenza degli altri (fusione e quick sort) non
richiede una ricorsività massiccia o vettori multipli.
Ciò ne fa l’alternativa più attrattiva per grandi insiemi di milioni di dati.
Come il nome suggerisce, all’inizio l’heap sort forma un mucchio
dall’insieme dei dati, quindi rimuove da esso l’elemento maggiore e
lo colloca alla fine del vettore ordinato.
Quindi ricostruisce il mucchio, rimuove l’elemento più grande e lo
colloca nella successiva posizione libera a partire dalla fine del
vettore ordinato.
Ripete questo procedimento fino a che non vi siano più elementi nel
mucchio e il vettore ordinato sia pieno.
Le implementazioni elementari richiedono due vettori: uno per
contenere il mucchio e l’altro gli elementi ordinati.
Per eseguire un ordinamento sul posto e risparmiare lo spazio che
sarebbe necessario per il secondo vettore, l’algoritmo seguente
“bara” usando lo stesso vettore per memorizzare sia il mucchio sia
il vettore ordinato.
Ogni qualvolta un elemento sia rimosso dal mucchio, esso libera uno
spazio alla fine del vettore, in cui l’elemento rimosso può essere
collocato.
I vantaggi dell’heap sort sono quindi l’ordinamento sul posto e la non
ricorsività, che lo rendono una buona scelta per insiemi di dati
estremamente grandi.
Per contro è più lento degli ordinamenti per fusione e quick sort.
Segue il codice della funzione spostaGiù, che costruisce e
ricostruisce il mucchio
Efficienza dell’algoritmo heap sort
Ordinamento per fusione (merge). Gli algoritmi di ordinamento
visti finora presentano lo svantaggio che i tempi di esecuzione
crescono molto in fretta al crescere del numero n di elementi da
ordinare.
Un metodo completamente diverso di ordinamento e assi più veloce
per n grande è l’ordinamento per fusione (merge sort), che viene
descritto in maniera semplice facendo uso della ricorsività.
Esso applica la tecnica del divide et impera, consistente nel
suddividere il problema di partenza in due problemi analoghi, ma di
minore ampiezza. In questo caso:
1. si divide il vettore iniziale a in due sotto-vettori di uguali
dimensioni, uno contenente le sue componenti di posto dispari
(a1, a3, a5, ...), l’altro quelle di posto pari (a2, a4, a6,
...);
2. si ordina separatamente ciascuno dei due sotto-vettori (in maniera
ricorsiva);
3. si fondono i due sotto-vettori ordinati.
1. Suddivisione. La suddivisione è un problema banale, e si ottiene
con il semplicissimo ciclo for seguente:
for (k = 1 ; k <= n/2 ; k ++)
b[k] = a[k*2];
Per risparmiare spazio, esso lascia le componenti di posto dispari
nel vettore iniziale a, limitandosi a copiare quelle di posto pari nel
vettore b.
A questo punto è opportuno rinumerare le componenti del sotto-vettore
a, in modo che gli indici coincidano con i primi termini della
successione dei numeri interi, per esempio con il seguente ciclo for:
for (k = 1 ; k <= n/2 ; k++)
a[k] = a[k*2 – 1];
2. Ordinamento. L’ordinamento può essere eseguito, per ciascuno
dei due sotto-vettori a[k], b[k], con uno qualsiasi dei metodi visti
in precedenza, tenendo conto delle relative osservazioni.
3. Fusione. Anche la fusione risulta particolarmente semplice, in
quanto si dispone ora di due vettori
a = a[1], ... , a[l]
e
b = b[1], ... , b[m]
aventi per componenti dei numeri interi ordinati.
Supponiamo che l’ordinamento sia non decrescente, cioè che risulti
a[i] <= a[i+1] e b[i] <= b[i+1]
per qualsiasi valore di i.
Si tratta di costruire un vettore v con l + m = n componenti in cui
compaiono tutte le componenti di a e di b ordinate nella stessa
maniera.
Un algoritmo che risolve questo problema può essere il seguente:
1. si confronta a[1] con b[1] e si pone il minore (o uno qualsiasi,
se sono uguali) in v[1].
2. se si è scelto a[1], si confronta a[2] con b[1],
altrimenti
si confronta a[1] con b[2],
3.si pone il minore in v[2].
Il procedimento continua fino a che si sono confrontate tutte le
componenti, dopo di che il vettore a è stato ordinato nel vettore v.
Osserviamo che l’ordinamento per fusione richiede un numero di
operazioni proporzionale a l + m = n.
Questo algoritmo presenta il vantaggio di essere leggermente più
veloce dell’ordinamento heap per grandi liste.
Per contro richiede almeno il doppio di memoria di altri metodi,
essendo di tipo ricorsivo.
Le implementazioni elementari fanno uso di tre vettori, uno per
ciascuna metà del vettore di partenza, e uno per il vettore ordinato.
L’algoritmo seguente fonde i vettori sul posto, cosicché sono
necessari solo due vettori.
Esistono versioni non ricorsive dell’ordinamento per fusione, ma sulla
maggior parte delle macchine non producono alcun significativo
miglioramento di prestazioni.
L’ordinamento per fusione si può eseguire in modo semplice se si
rappresenta l’elenco dei dati da ordinare nella forma non già di un
vettore, ma di una lista concatenata.
Questa è una struttura dati che si può pensare costituita da tante
celle o record, ciascuna delle quali è suddivisa in due sotto-celle o
campi.
Le celle sono rappresentate da rettangoli, la cui parte sinistra
contiene un dato della lista, mentre la parte destra contiene un
puntatore, rappresentato da una freccia.
Il puntatore è un dato che viene interpretato come l’indirizzo del
record che segue quello attuale nell’ordinamento della lista.
Un punto al posto di un puntatore indica che quel record non punta
ad altri record.
In tal modo risulta particolarmente semplice non solo cambiare
l’ordine dei dati, ma anche eseguire su di essi le fondamentali
operazioni di
• inserimento
• cancellazione
• ricerca.
Efficienza dell’algoritmo di ordinamento per fusione
Quicksort. Sebbene l’algoritmo shell sort sia decisamente migliore
di quello per inserimento, non lo è in senso assoluto.
Infatti il migliore metodo di ordinamento per vettori fino a oggi
conosciuto è senz’altro l’algoritmo pubblicato nel 1961 da C.A.R.
Hoare.
Le sue prestazioni sono così spettacolari che il suo inventore lo
chiamò Quicksort (ordinamento veloce).
Quicksort partiziona il vettore da ordinare in due sezioni, la prima di
elementi “piccoli”, la seconda di elementi “grandi”. Quindi ordina
separatamente gli elementi piccoli e i grandi, in modo ricorsivo.
Idealmente il partizionamento dovrebbe avvenire rispetto a un
elemento, detto pivot, che sia la mediana dei valori dati.
Poiché però la ricerca della mediana richiede la scansione dell’intero
vettore, e ciò rallenterebbe l’algoritmo, si può scegliere per
semplicità come pivot l’elemento che occupa il posto mediano del
vettore.
Nell’esempio seguente viene selezionato come pivot l’elemento del
vettore contenente il valore 42.
Quindi si fa scorrere un indice, min, a partire dall’estremità sinistra
del vettore fino a che incontra il primo elemento maggiore del pivot
(in questo caso il 44), e un indice, max, a partire dall’estremità
destra fino a che incontra il primo elemento minore del pivot (in
questo caso il 18).
Questi due elementi vengono scambiati fra loro, dando luogo alla
situazione seguente:
Il processo viene quindi ripetuto facendo scorrere gli indici verso il
pivot, e individuando gli elementi 55 e 06
Anch’essi vengono scambiati, dando luogo alla situazione seguente:
Nel passo successivo i due indici min e max vengono a coincidere, e
ciò determina la fine del processo, con tutti gli elementi a sinistra del
pivot <= di esso, e tutti gli elementi alla sua destra >= di esso.
Quindi, come si suole dire, il vettore a è stato partizionato.
Il programma a fianco
chiede di scrivere 8
numeri da tastiera,
assume come pivot il
quarto ed esegue su
essi il partizionamento
indicato in
precedenza:
#include <stdio.h>
#define NUMEL 8
void main(void)
{
int min, max, pivot, temp, a[NUMEL];
for (min = 0; min < NUMEL; min++)
{
printf("Scrivi un numero: ");
scanf("%d", &a[min]);
}
min = 0;
max = NUMEL-1;
pivot = a[3];
while (min < max)
{
while (a[min] < pivot)
min ++;
while (a[max] > pivot)
max --;
temp = a[min];
a[min] = a[max];
a[max] = temp;
min ++;
max --;
}
for (min = 0; min < NUMEL; min++)
printf("\n%d ", a[min]);
}
Naturalmente a questo punto il vettore non è stato ancora ordinato,
ma solo partizionato.
Per ottenere l’ordinamento sarà però sufficiente applicare questo
procedimento a entrambe le partizioni ottenute, poi alle partizioni
delle partizioni e così via, fino a quando ogni partizione sarà
costituita da un solo elemento.
Per meglio comprendere la struttura del programma definitivo,
conviene scrivere un programma intermedio, che esegue il
partizionamento chiamando dall’interno della funzione principale
una funzione quickSort.
Questa si ottiene riscrivendo il programma precedente senza le
istruzioni di ingresso e uscita, che vanno invece riportate nel
programma principale.
Avremo quindi il seguente programma:
#include <stdio.h>
#define NUMEL 8
void main(void)
{
int i, a[NUMEL];
int quickSort(int []);
/* dichiara quickSort */
for (i=0; i < NUMEL; i++)
{
printf("Scrivi un numero: ");
scanf("%d", &a[i]);
}
quickSort(a);
/* chiama quickSort */
for (i = 0; i < NUMEL; i++)
printf("\n%d ", a[i]);
}
/* definisce la funzione quickSort */
int quickSort(int a[])
{
int min, max, pivot, temp;
min = 0;
max = NUMEL-1;
pivot = a[3];
while (min < max)
{
while (a[min] < pivot)
min ++;
while (a[max] > pivot)
max --;
temp = a[min];
a[min] = a[max];
a[max] = temp;
min ++;
max --;
}
}
Osserviamo che all’interno della funzione main() la funzione
quickSort è dichiarata (con l’istruzione int quickSort (int
[]);) in modo da ricevere come parametro un vettore di interi e
fornire un risultato intero (in questo caso un vettore).
A questo punto, il programma precedente va riscritto in modo che
effettui una chiamata ricorsiva alla funzione di ordinamento.
Vedremo più avanti il listato completo.
Per assegnare un valore al pivot, la funzione q_sort sceglie
semplicemente il primo elemento (a[min]). I restanti elementi del
vettore sono confrontati con il pivot, e messi alla sua sinistra o alla
sua destra a seconda del loro valore.
Efficienza. Quicksort è un algoritmo di ordinamento non-stabile e
non sul posto, in quanto richiede spazio nello stack.
Esso risulta poco efficiente nel caso in cui il vettore sia già ordinato.
In tale caso la funzione q_sort selezionerebbe l’elemento minore
come valore da assegnare al pivot e dividerebbe il vettore con un
elemento nella partizione di sinistra, e max-min elementi nell’altra.
Ogni chiamata ricorsiva a q_sort ridurrebbe solo di un’unità la
dimensione del vettore da ordinare. Sarebbero quindi necessarie n
chiamate ricorsive per effettuare l’ordinamento, portando a un
tempo di esecuzione di O(n2).
Se però si scegliesse a caso un elemento come pivot, sarebbe
estremamente improbabile il verificarsi del caso peggiore.
Se poi il pivot fosse la mediana di tutti i valori, che divide il vettore in
due parti uguali, il vettore verrebbe diviso in due a ogni passo, e il
tempo di esecuzione sarebbe O(n * lg n).
Quindi Quicksort ha complessità O(n * lg n) nel caso medio, e
O(n2) nel caso peggiore.
Efficienza dell’algoritmo quick sort
Miglioramenti. All’algoritmo Quicksort di base si possono apportare
diversi miglioramenti:
1. Nella funzione q_ sort si sceglie come pivot l’elemento centrale.
Se la lista è parzialmente ordinata, questa risulta una buona
scelta. Il caso peggiore si verifica quando l’elemento centrale è
l’elemento più piccolo o più grande a ogni chiamata a q_sort.
2. Per vettori piccoli viene chiamata la funzione insertSort.
A causa della ricorsività e di altri costi addizionali, Quicksort non
è un algoritmo efficiente su vettori di piccole dimensioni. Di
conseguenza, ogni vettore con meno di 12 elementi viene
ordinato usando l’ordinamento per inserimento. Il valore ottimale
di questa soglia non è critico, e varia con la qualità del codice
generato.
3. Si ha ricorsività di coda quando l’ultima istruzione di una funzione è
una chiamata alla funzione stessa. La ricorsività di coda può essere
sostituita dall’iterazione, ottenendo un utilizzo migliore dello stack.
4. Dopo che il vettore è stato partizionato, la partizione più piccola
viene ordinata per prima. Ciò determina un migliore utilizzo dello
stack, considerato che le partizioni più piccole sono ordinate - e
quindi eliminate - più velocemente.
La tabella seguente mostra le statistiche di tempo e l’uso dello stack
prima e dopo l’introduzione dei miglioramenti.
elementi
tempo (µs)
prima
dimensione stack
dopo
prima
dopo
16
103
51
540
28
256
1.630
911
912
112
4.096
34.183
20.016
1.908
168
65.536
658.00
3
460.73
7
2.436
252
Confronto. Come conclusione confrontiamo i principali algoritmi di
ordinamento trattati: per inserimento, shell sort, e quicksort. Ci sono
molti fattori che influenzano la scelta di un algoritmo di ordinamento:
 Ordinamento stabile. Ricordate che un algoritmo di ordinamento
stabile lascia gli elementi uguali nella stessa posizione relativa al
termine dell’ordinamento. L’ordinamento per inserimento è l’unico
algoritmo stabile fra quelli trattati.
 Spazio. Un algoritmo sul posto non richiede memoria aggiuntiva per
portare a termine l’ordinamento. Sia l’ordinamento per inserimento
sia shell sort sono algoritmi sul posto. Quicksort richiede spazio
nello stack per la ricorsività, quindi non è un algoritmo sul posto.
L’invenzione di artifici ha ridotto notevolmente il tempo richiesto
dall’algoritmo.
• Tempo. Non è difficile che il tempo richiesto per ordinare un insieme
di dati raggiunga ordini di grandezza astronomici, come abbiamo
visto nella tabella delle funzioni di n. La tabella seguente mostra le
complessità relative di ogni metodo.
istruzioni
complessità
media
complessità
del caso peggiore
inserimento
9
O(n2)
O(n2)
shell sort
17
O(n1.25)
O(n1.5)
quicksort
21
O(n lg n)
O(n2)
metodo
Nella tabella seguente sono riportati i tempi di ordinamento, partendo
da un insieme di dati ordinati in modo casuale.
elementi
da ordinare
inserimento
16
39 µs
256
4.969 µs
4.096
1,315 sec
65.536 416,437 sec
shell
quicksort
45 µs
51 µs
1.230 µs
911 µs
0,033 sec 0,020 sec
1,254 sec 0,461 sec
Semplicità. La tabella dellavideata precedente mostra il numero di
istruzioni necessarie per ogni algoritmo. Algoritmi più semplici portano
a meno errori in fase di codifica.
Ordinamento esterno
GIi algoritmi di ordinamento visti finora prevedevano tutti i seguenti
passi:
• caricare i dati in memoria
• ordinare i dati (in memoria), quindi
• scrivere i risultati.
Essi non possono venire applicati quando i dati da ordinare non
trovano posto nella memoria principale del computer e sono,
invece, memorizzati in un dispositivo periferico di memoria
secondaria, per esempio un’unità a nastro.
In questo caso i dati sono rappresentati con un file sequenziale, la cui
caratteristica è di rendere accessibile una, e una sola, componente
in qualsiasi momento.
Si tratta di una severa restrizione, a confronto con le possibilità che
offre la struttura vettore, che richiede una tecnica di ordinamento
esterno.
La tecnica più importante è l’ordinamento per fusione, che combina
due (o più) sequenze ordinate in una sola mediante ripetute
selezioni tra le componenti che sono correntemente accessibili.
L’algoritmo di ordinamento detto fusione diretta consiste nei
seguenti quattro passi:
1. si suddivide la sequenza a in due metà, chiamate b e c;
2. si fondono b e c combinando elementi singoli in coppie ordinate;
3. detta a la sequenza ottenuta, si ripetono i passi 1 e 2, questa
volta fondendo coppie ordinate in quadruple ordinate;
4. si ripetono i passi precedenti, fondendo quadruple in ottuple e
così si continua, raddoppiando ogni volta la lunghezza delle
sottosequenze che vengono combinate, fino al completo
odinamento della sequenza iniziale.
Consideriamo, per esempio, la seguente lista
Nel passo 1. essa viene suddivisa nelle nelle due sequenze
La fusione delle singole componenti (che sono
sequenze ordinate di lunghezza 1) in coppie
ordinate dà luogo a
Suddividendo un’altra volta
nel mezzo e combinando le
coppie ordinate otteniamo:
Una terza suddivisione, seguita dalla fusione,
produce finalmente il risultato desiderato:
Ogni operazione che tratta l’intero insieme dei dati viene chiamata
fase. Il più piccolo sottoprocesso che, per ripetizione, costituisce il
processo di ordinamento, viene chiamato passata o stadio.
Nell’esempio precedente sono state necessarie tre passate per
ordinare, ognuna delle quali era costituita da una fase di
suddivisione e da una di fusione.
Per potere eseguire l’ordinamento sono necessari tre nastri; perciò
il processo viene chiamato fusione con tre nastri.
Fusione bilanciata (a una fase). In verità, le fasi di suddivisione non
contribuiscono all’ordinamento, poiché esse non permutano in alcun
modo gli elementi. In un certo senso, sono azioni improduttive, anche
se costituiscono la metà di tutte le azioni di copia.
Ebbene, le fasi di suddivisione possono essere eliminate, combinandole
con quelle di fusione.
Invece di creare una sola sequenza, il risultato del processo di fusione
viene immediatamente redistribuito su due nastri, che saranno le
sorgenti per la passata successiva.
Questo metodo viene chiamato ordinamento per fusione bilanciata o
fusione a una fase, in antitesi al precedente ordinamento a due fasi.
È evidente che il nuovo metodo è superiore al vecchio, perché necessita
solo della metà di operazioni di copia.
Il prezzo di questo miglioramento è un quarto nastro.
Bibliografia
Aho, Alfred V. and Jeffrey D. Ullman [1983].
Data Structures and Algorithms.
Addison-Wesley, Reading, Massachusetts.
Cormen, Thomas H. [2001].
Introduction to Algorithms.
McGraw-Hill, New York.
Knuth, Donald E. [1998].
The Art of Computer Programming, Volume 3, Sorting
and Searching.
Addison-Wesley, Reading, Massachusetts.
Pearson, Peter K. [1990].
Fast Hashing of Variable-Length Text Strings.
Communications of the ACM, 33(6):677-680, June 1990.
Pugh, William [1990].
Skip Lists: A Probabilistic Alternative to Balanced Trees.
Communications of the ACM, 33(6):668-676, June 1990.
Algoritmo di cifratura RSA
L’algoritmo RSA è stato pubblicato nel 1978 da R. L. Rivest, A.
Shamir e L. Adelman (da cui il nome), sebbene la sua prima
descrizione si debba a James H. Ellis (1970) e le sue prime
implementazioni pratiche a C. C. Cocks (1973) e Malcom J.
Williamson (1974).
Ellis, Cocks e Williamson lavoravano all’epoca nel Communications
Electronics Security Group delle forze armate britanniche.
RSA è il più moderno algoritmo di cifratura, ed è applicato per
garantire un elevato livello di sicurezza ai cosiddetti documenti
elettronici, in particolare nel caso di trasmissione attraverso reti
telematiche.
La cifratura avviene di solito sostituendo i caratteri di cui è composto
un messaggio m, detto messaggio in chiaro, con altri in base a un
determinato criterio, detto chiave; si produce così un messaggio
cifrato c.
L’operazione inversa di decifrazione avviene sostituendo i caratteri del
messaggio cifrato c in modo da riottenere quello originario in chiaro
m.
Questa seconda operazione può essere effettuata usando la stessa
chiave impiegata per la cifratura – e allora si parla di chiavi
simmetriche – oppure una chiave diversa - e allora si parla di chiavi
asimmetriche.
L’algoritmo RSA è di tipo asimmetrico, in quanto usa due chiavi
diverse, una per cifrare i messaggi, l’altra per decifrarli; ciò fa sì che
il mittente e il destinatario non si debbano scambiare la chiave di
cifratura/decifrazione prima di potere comunicare, con un evidente
vantaggio in termini di sicurezza.
Infatti la chiave di cifratura può tranquillamente essere resa pubblica,
ad es. mettendola a disposizione su Internet o stampandola su un
bollettino, in quanto la sua conoscenza non permette affatto (o
permette con molta difficoltà) di risalire alla chiave di decifrazione,
che deve invece rimanere privata (cioè segreta).
In altri termini, la conoscenza della chiave pubblica di una persona A
permette a chiunque di mandare un messaggio cifrato ad A,
messaggio che solo A potrà decifrare con la propria chiave privata,
ma non fornisce alcuna informazione sulla chiave privata di A.
La cifratura di un testo richiede dapprima che esso sia convertito in
una serie di numeri (digitalizzazione); questi potrebbero essere per
esempio i codici ASCII o EBCDIC dei suoi caratteri.
A questo punto, come indica la figura,
il mittente A usa la chiave pubblica del destinatario B per cifrare il
messaggio m da inviargli; ottiene così il messaggio cifrato c, che può
essere inviato senza alcuna precauzione a B.
Questi impiega la propria chiave privata per decifrare il messaggio
cifrato c, ricostruendo quello originario m.
Costruzione della coppia di chiavi asimmetriche. La costruzione
delle due chiavi di cifratura e decifrazione si basa sul fatto che,
mentre è abbastanza semplice moltiplicare tra loro due numeri
primi anche molto grandi, l’operazione inversa di trovare i fattori
primi di un numero abbastanza grande è assai più difficile.
La costruzione avviene attraverso i seguenti passi:
1. si moltiplicano tra loro due numeri primi p, q sufficientemente
grandi, ottenendosi come prodotto il numero n
[per fare un esempio semplice, supponiamo p = 3, q = 5,
quindi p*q = n = 15]
2. si sceglie un intero D che non sia divisibile né per p-1 né per
q-1
[nel nostro esempio scegliamo D = 11, che non è divisibile né
per 2 né per 4].
3. si calcola un intero E tale che il resto della divisione di E*D per
(p-1)*(q-1) sia uguale a 1[1].
Ciò equivale a risolvere il seguente problema:
Trovare un valore di k tale che l’espressione
k*(p-1)*(q-1)+1
E = --------------D
abbia un valore intero
Osserviamo che tale equazione è detta diofantea, e non può essere
risolta con una formula, ma solo per tentativi, cioè sostituendo a k i
successivi valori 1, 2, 3,... finché si trova per E un valore intero.
[1]
Ricordiamo che la funzione modulo, indicata con mod, indica il resto della
divisione di due numeri interi. Perciò la precedente condizione si esprime
dicendo che deve risultare E*D = 1 mod(p-1)*(q-1)
L’operazione si può eseguire automaticamente con un programma di
foglio elettronico, trovandosi le soluzioni dell’equazione indicate in
tabella.
k
E
4
15
26
37
...
3
11
19
27
...
Scegliamo, ad es., k = 4 a cui corrisponde E = 3.
La chiave pubblica di cifratura, da comunicare, è la coppia
(E,n).
La chiave privata di decifrazione, da tenere segreta, è la coppia
(D,n).
Cifratura e decifrazione. Il messaggio cifrato, c, è il resto della
divisione di mE per n [1].
Il messaggio originario, m, è il resto della divisione di cD per n [2].
Se scegliamo come chiave pubblica la coppia
(E = 3, n = 15)
come chiave privata la coppia
(D = 11, n = 15)
e come messaggio m i primi 10 numeri interi, otteniamo i valori
indicati in Tabella.
[1]
In termini matematici ciò si esprime dicendo che c = mE mod n
[2] In termini matematici ciò si esprime dicendo che m = cD mod n
Mettiamoci adesso dalla parte di un cracker il quale intercetti il
messaggio cifrato, c, e voglia da esso ricavare il messaggio
originario, m.
Dato che egli sa che E=3 e che n=15, tutto ciò di cui ha bisogno
è di conoscere i due numeri primi, p, q, che moltiplicati tra loro
danno 15.
Infatti dalla conoscenza di p, q, troverebbe p-1 (=2) e q-1 (=4),
e da essi risalirebbe facilmente al numero D, non divisibile né
per 2 né per 4.
Come abbiamo visto, una volta trovato D il messaggio originario,
m, si ottiene da quello cifrato, c, dalla formula
m = mod(cD, n)
già usata nella Tabella precedente.
Ebbene, la inviolabilità dei messaggi cifrati con l’algoritmo RSA
risiede proprio nella difficoltà di fattorizzare numeri che siano il
prodotto di numeri primi molto grandi (ricordiamo che di recente
è sato scoperto il numero primo più grande, lungo oltre 9 milioni
di caratteri).