Questo sito contribuisce alla audience di

Cenni di teoria della complessità e teoria dei numeri

Cenni di teoria della complessità e teoria dei numeri. Appendice della tesi di laurea in "Applicazione delle tecniche di crittografia nella trasmissione ed elaborazione dati" redatta dall'ingegnere Federico Gennari nell'anno accademico 2000/2001.

APPENDICE 1: cenni di teoria della complessità e teoria dei numeri

La finalità principale della teoria della complessità è di fornire strumenti per classificare problemi di calcolo secondo le risorse necessarie per risolverlo (essenzialmente il tempo, talvolta anche la memoria), basandosi essenzialmente sulla difficoltà intrinseca del problema piuttosto che sul particolare modello di calcolo.

Suddetti problemi saranno risolti medianti algoritmi, il cui tempo di lavoro è il numero di operazioni elementari che esso deve compiere per arrivare alla soluzione (operazioni binarie, comparazioni, istruzioni macchina ecc.). In genere si usa il tempo nel caso peggiore, essendo un limite superiore, in funzione della grandezza dell’ingresso, ma ci si può riferire anche al tempo medio (sempre in funzione dell’ingresso) e al tempo asintotico, ovvero quando l’ingresso cresce all’infinito.

Un algoritmo a tempo polinomiale è un algoritmo il cui tempo nel caso peggiore che è una funzione dell’ordine O(nk), dove n è la dimensione dei dati di ingresso e k una costante. Un algoritmo il cui tempo di lavoro non è polinomiale è chiamato a tempo esponenziale, ed è considerato inefficiente.

Un algoritmo a tempo sub-esponenziale ha un tempo di lavoro nel caso peggiore è una funzione del tipo eo(n). Esso è asintoticamente più veloce di uno a tempo esponenziale pieno ma asintoticamente più lento di uno a tempo polinomiale.

La classe di complessità P è l’insieme di tutti i problemi di decisione (problemi la cui risposta è si/no, a cui ci limitiamo per facilità ma i cui algoritmi possono essere estesi ai problemi computazionali) che sono risolvibili in tempo polinomiale.

La classe di complessità NP è l’insieme di tutti i problemi decisionali per cui la risposta SI può essere verificata in un tempo polinomiale avendo una informazione extra detta certificato (non è detto che però sia semplice ottenerlo).

La classe di complessità co-NP è l’analogo del precedente, ma riguardante la risposta NO.

Esempio Proposizione: n è un numero intero.

Domanda: n è composto? Cioè, esistono a,b>1 tali che n=ab?

I composti appartengono a NP perché se un intero n è composto può essere verificato in tempo polinomiale se viene dato il certificato divisore a (1n). Analogamente appartengono a co-NP.

Elenchiamo adesso una serie di risultati della teoria dei numeri con applicazioni alla crittografia:

Teorema fondamentale dell’aritmetica;

Complessità computazionale delle quattro operazioni base;

Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due interi;

Se a e b sono interi, allora a è detto essere congruente a b modulo n, scritto (mod n), se n divide (a - b). L’intero n è chiamato modulo della congruenza.

Generalizzazione d’Eulero del Teorema di Fermat: se N=pq, con sia p che q numeri primi, definendo ø(N)=(p-1)(q-1), allora Xø(N) = 1 mod N è vera per tutti gli X non divisibili per p e q (cioè sono primi tra loro, MCD (X, ø(N) )=1).

Teorema del resto Cinese (CRT)

Algoritmo di Gauss: produce la soluzione x del Teorema del resto Cinese, calcolato come(dove Ni=n/ni e M = Ni-1) in O( (lg n)2) operazioni su bit.

Sia n2 un intero:

(teorema di Eulero) se aZn*, allora
se n è un prodotto di primi distinti, e se , allora per tutti gli interi a. In altre parole, quando si lavora modulo n, gli esponenti possono essere ridotti modulo .
Tabella della complessità delle operazioni base su bit in Zn





















Operazione


Complessità in bit


Addizione modulare (a + b) mod n


O(lg n)


Sottrazione modulare (a – b) mod n


O(lg n)


Moltiplicazione modulare (a b) mod n


O((lg n) 2 )


Inversione modulare a -1 mod n


O((lg n) 2 )


Esponenziale modulare a k mod n, k


O((lg n) 3 )

L’insieme di Zn è rappresentato dagli interi {0, 1, 2, …, n - 1}, con le seguenti operazioni

Somma modulare (a + b)= a+b (se a+b<n)
a+b-n (se )

Esponenziale modulare può essere eseguito efficientemente con l’algoritmo quadra-e-moltiplica (square-and-root) ripetuto, che è cruciale in molti protocolli crittografici. Una versione dell’algoritmo è basato sulla rappresentazione dei numeri in base 2, ad esempio del numero k
(dove ki {0,1})

Algoritmo di quadra-e-moltiplica ripetuto per esponenziali in Zn ;
Simbolo di Legendre e Simbolo di Jacobi;
Strutture algebriche;

La sicurezza di molti codici a chiave pubblica si basa sulla presunta intrattabilità dei problemi computazionali elencati sommariamente nella tabella seguente. Parlando non rigorosamente un problema è facile o trattabile se può essere risolto in tempo polinomiale, almeno per una frazione non trascurabile degli ingressi possibili. In altre parole, se c’è un algoritmo che può risolvere una frazione non trascurabile di tutte le istanze di un problema in tempo polinomiale, allora un qualsiasi crittosistema la cui sicurezza è basata su quel problema deve essere considerato insicuro. I problemi di calcolo qui elencati hanno una complessità reale non conosciuta, cioè sono ampiamente considerati intrattabili (se si scelgono bene i parametri del problema) sebbene non ci sia ancora una prova univoca. Generalmente, il solo limite inferiore conosciuto sulle risorse richieste per la soluzione sono banali limiti lineari, che non forniscono una prova della loro intrattabilità. Per questa ragione sono state escogitate varie tecniche di riduzione di un problema computazionale in un altro: queste riduzioni forniscono un mezzo per convertire un algoritmo che risolve il secondo problema in un algoritmo per la soluzione del primo e sono studiate in letteratura (si veda la bibliografia maggiori notizie).

































Problema


Descrizione


FATTORIZZAZIONE


Problema della fattorizzazione intera: dato un intero positivo n, trovare la sua fattorizzazione n = p1e1p2e2… pkek (dove pi sono numeri primi distinti e gli ei interi positivi 1)


RSAP


Problema RSA (noto anche come Inversione di RSA): dato un intero positivo n che è prodotto di due primi dispari distinti p e q, un intero positivo e tale che MCD(e, (p-1)(q-1)=1, e un intero c, trovare un intero m tale che mec (mod n).


QRP


Problema del resto quadratico: da un intero dispari composto n ed un intero a avente simbolo di Jacobi , decidere se a è un residuo quadratico modulo n o meno


SQROOT


Radice quadrata modulo n: da un intero composto n e a (l’insieme dei redsiui quadratici modulo n), trovare una radice quadra di a modulo n; cioè un intero x tale che.


DLP


Problema del logaritmo discreto: dato un numero primo p, un generatore e un elemento , trovare l’intero x, , tale che .


GDLP


Problema del logaritmo discreto generalizzato: dato un gruppo ciclico finito G di ordine n, un generatore e un elemento , trovare un intero x, , tale che .


DHP


Problema Diffie-Hellman: dato un numero primo p, un generatore e gli elementi e , trovare .


GDHP


Problema Diffie-Hellman generalizzato: dato un gruppo ciclico finito G, un generatore e un gruppo di elementi e , trovare .


SUBSET-SUM


Problema della somma di sottoinsiemi: dato un insieme di interi positivi{a1, a2,…, an}e un intero positivo s, determinare se c’è o meno un sottoinsieme di aj la cui somma è s