Permutazione

PERMUTAZIONE

La permutazione è un modo di ordinare in successione più oggetti distinti come nell'anagrammare una parola: in termini matematici, una permutazione di un insieme X si definisce come una funzione biiettiva p: X→X.

Il numero delle permutazioni di n oggetti è pari al fattoriale di n, vale a dire:

n! = n · (n-1) · (n-2) · ... · 1.

Infatti, ci sono n modi di scegliere l'oggetto che occupa la prima posizione, poi, per ciascuno di essi, ci sono n-1 modi di scegliere l'oggetto che occupa la seconda posizione, poi, per ogni coppia di oggetti fissati nelle prime due posizioni, ci sono n-2 modi di scegliere l'oggetto nella terza posizione, e così via, fino ad occupare tutte le posizioni.

Ad esempio, le permutazioni possibili della serie di 4 lettere "ABCD" sono 24, e si presentano come:

ABCD BACD CABD DABC

ABDC BADC CADB DACB

ACBD BCAD CBAD DBAC

ACDB BCDA CBDA DBCA

ADBC BDAC CDAB DCAB

ADCB BDCA CDBA DCBA

Sistema robusto

Se con 4 lettere sono possibili 24 permutazioni, con 64 bit ne sono possibili ben 1,3 · 10 ,ma per il nostro algoritmo crittografico, 2 = 65536 rappresenta già una buona quantità: basti pensare che un'immagine binaria di 256 bit, crittabile con 1,8 · 10 differenti permutazioni, procurerebbe un ininterrotto lavoro di almeno 6,5 anni circa ad un calcolatore capace di provare 90 miliardi di chiavi al secondo per trovare la giusta permutazione.

Di seguito vi è un'illustrazione di un array di 16 elementi ordinato (al centro), poi permutato con una permutazione P (in alto) e infine permutato con la sua permutazione inversa P

(in basso):

-1

Come si può notare, il calcolo si basa su due dati: valore precedente (BIT) e attuale (POS) dell'indice di ogni elemento dell'array: tramite essi, si può definire la permutazione P inversa della permutazione Q se e solo se BITP = POSQ e BITQ = POSP.

Di seguito, vi è un link ad un'applicazione pratica di quanto spiegato finora sulla permutazione:

Infine, al link qui in basso viene illustrato il processo di comunicazione: