Numero di Gödel

Questa voce o sezione sull'argomento logica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

In logica matematica, una numerazione di Gödel è una funzione che assegna a ciascuna produzione di un linguaggio formale un unico numero naturale chiamato numero di Gödel. Il concetto fu ideato da Kurt Gödel nel suo teorema di incompletezza.

La cifratura secondo il metodo di Godel si basa sulla fattorizzazione secondo il seguente principio:

${\displaystyle Messaggio=(P_{1}^{Pos_{1}})(P_{2}^{Pos_{2}})(P_{3}^{Pos_{3}})...(P_{n}^{Pos_{n}})}$

Dove ${\displaystyle P_{n}}$ è il numero primo successivo a ${\displaystyle P_{n-1}}$ e ${\displaystyle Pos_{n}}$ è la posizione dell'${\displaystyle n}$-esima lettera nell'alfabeto preso in considerazione.

Ad esempio:

${\displaystyle ABA=(2^{1})*(3^{2})*(5^{1})=2*9*5=90}$

Per decrittare basta eseguire la scomposizione in fattori primi del numero ottenuto; gli esponenti indicano la posizione della lettera nell'alfabeto.

${\displaystyle 90=2^{1}*3^{2}*5^{1}}$

Gli esponenti sono 1, 2 e 1; il messaggio è quindi A, B, A.

Il punto debole di questo algoritmo è la facilità di decrittatura: basta scomporre in fattori primi. Per aggirare il problema si può combinare una sostituzione polialfabetica per renderlo molto sicuro. Lo svantaggio è che si deve lavorare su numeri molto grandi.

Esempio:

${\displaystyle CIAO=3.7*10^{18}}$

Un modo per risolvere quest'ultimo problema è dividere la stringa in tanti pezzi così da avere numeri più maneggevoli.

Per esempio:

CIAO = CI-AO

${\displaystyle CI=(2^{3})*(3^{9})=8*19683=157464}$

${\displaystyle AO=(2^{1})*(3^{15})=2*14348907=28697814}$

${\displaystyle CIAO=157464.28697814}$

Usando questo metodo si può combinare una doppia cifratura polialfabetica o monoalfabetica: una prima della gödelizzazione, un'altra dopo (usando come chiave i numeri ottenuti o sostituendo il numero con la posizione della lettera nell'alfabeto).

Esempio:

CIAO = 157464.28697814

MESSAGGIO CIFRATO = MQSPRP.NTRUSTMP

• (EN) Gödel number, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• Articolo archiviato di programmazione.it sui possibili utilizzi del Numero di Gödel per la compressione, su programmazione.it. URL consultato il 3 novembre 2021 (archiviato dall'url originale l'8 settembre 2014).

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica