Numărul Gödel

În logica matematică , o numerotare Gödel este o funcție care atribuie fiecărei producții a unui limbaj formal un număr natural unic numit numărul Gödel . Conceptul a fost conceput de Kurt Gödel în teorema incompletitudinii sale.

Utilizare în criptografie

Codificarea conform metodei Godel se bazează pe factorizare în conformitate cu următorul principiu:

$Messaggio=(P_{1}^{Pos_{1}})(P_{2}^{Pos_{2}})(P_{3}^{Pos_{3}})...(P_{n}^{Pos_{n}})$ ${\ displaystyle Message = (P_ {1} ^ {Pos_ {1}}) (P_ {2} ^ {Pos_ {2}}) (P_ {3} ^ {Pos_ {3}}) ... (P_ { n} ^ {Pos_ {n}})}$ $Mesaj = (P_1 ^ {Pos_1}) (P_2 ^ {Pos_2}) (P_ {3} ^ {Pos_3}) ... (P_ {n} ^ {Pos_n})$

Unde este $P_{n}$ ${\ displaystyle P_ {n}}$ $P_ {n}$ este numărul prim următor $P_{n-1}$ ${\ displaystyle P_ {n-1}}$ $P _ {{n-1}}$ Și $Pos_{n}$ ${\ displaystyle Pos_ {n}}$ $Pos_n$ este poziția $n$ ${\ displaystyle n}$ $n$ - a treia literă din alfabet luată în considerare.

De exemplu:

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

Pentru a decripta este suficient să se efectueze factorizarea primă a numărului obținut; exponenții indică poziția literei în alfabet.

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

Exponenții sunt 1, 2 și 1; mesajul este deci A, B, A.

Punctul slab al acestui algoritm este ușurința decriptării: doar factorul în factorii primi. Pentru a rezolva această problemă, puteți combina o substituție polialfabetică pentru a o face foarte sigură. Dezavantajul este că trebuie să lucrați la un număr foarte mare.

Exemplu:

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

O modalitate de a rezolva această ultimă problemă este împărțirea șirului în mai multe bucăți pentru a avea numere mai ușor de gestionat.

De exemplu:

BUNA = CI-AO

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

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

$CIAO=157464.28697814$ ${\ displaystyle HELLO = 157464.28697814}$ $BUNA = 157464.28697814$

Folosind această metodă puteți combina un dublu cifru polialfabetic sau monoalfabetic : unul înainte de gödelizare , altul după (folosind numerele obținute ca cheie sau înlocuind numărul cu poziția literei din alfabet).

Exemplu:

BUNA = 157464.28697814

Poziţie	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
Alfabet cifrat	M.	Nu.	SAU	P.	Î	R.	S.	T.	U	V.	W	X	Da	Z	LA	B.	C.	D.	ȘI	F.	G.	H.	THE	J	K.	L

MESAJ CIFRAT = MQSPRP.NTRUSTMP

linkuri externe

Articol despre programare.it despre posibilele utilizări ale numărului Gödel pentru compresie , pe programare.it .

Controlul autorității	LCCN ( EN ) sh85055600

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică