Problemi difficili

Tutti gli algoritmi di cifratura si basano su problemi difficili della teoria dei numeri, qui elencati alcuni esempi interessanti:

Fattorizzazione di un numero primo

*dato un numero primo $p$ trovare i numeri primi $x_i$ e i coefficienti $k_i$ tali per cui

$p={\sum }_i{k}_i{x}_i$

Calcolo del logaritmo discreto

dato un numero primo $p$ un generatore $g$ e un numero intero $A$ trovare $x$ tale per cui $A=g^x\mathrm{mod}p$ Tale problema ha una complessità sub-esponenziale per $p$ grande

NEXT