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