Problema della Fattorizzazione dei numeri interi

Il Problema della Fattorizzazione dei numeri interi (Integer Factorization Problem - IFP) può essere formulato come segue: dato un intero positivo n, trovare la sua fattorizzazione in numeri primi, ovvero scomporre il numero n in

(1)
\begin{align} n = p_1^{k_1} p_2^{k_2} \dots p_i^{k_i} \end{align}

dove p1, …, pi sono numeri primi distinti tra loro e k1, …, ki sono interi maggiori o uguali a 1.

Connesso al problema IFP, è stato formulato il Problema RSA (RSA Problem - RSAP) seguente: dato un intero n prodotto da due numeri primi p e q, un intero positivo e coprimo con il numero (p-1)(q-1) (ovvero il M.C.D. tra e e (p-1)(q-1) è 1), e un intero c, trovare un numero intero m tale che

(2)
\begin{align} m^e\:mod\:n = c \end{align}

Il Problema RSA è alla base degli algoritmi RSA per la crittografia, sia cifratura che firma digitale. Il Problema della Fattorizzazione è invece legato direttamente al sistema crittografico di Rabin.

Si può dimostrare che

(3)
\begin{align} RSAP \leq_p IFP \end{align}

ovvero, il problema RSA può essere riducibile in tempo polinomiale al problema della fattorizzazione: il problema RSA non è più difficile di quello della fattorizzazione. Se si riuscisse a risolvere efficientemente il problema della fattorizzazione allora si potrebbe riuscire a risolvere efficientemente anche il problema RSA. Il concetto di riduzione polinomiale corrisponde all'esistenza di un algoritmo che in tempo polinomiale può ridurre le istanze del problema RSA in istanze del problema di fattorizzazione.

Si deve notare che non è stata dimostrata l'equivalenza tra i due problemi.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License