Descompunerea în factori primi

În teoria numerelor descompunerea în factori primi sau factorizarea întregilor reprezintă procesul de aflare a divizorilor primi ai unui număr compus.

$x={a_{1}}^{p_{1}}\cdot {a_{2}}^{p_{2}}\cdot ...\cdot {a_{k}}^{p_{k}}$, unde a1, a2, ... , a3 sunt numere prime distincte

Aceasta pare a fi o problemă banală, dar pentru numere foarte mari nu se cunoaște niciun algoritm eficient de factorizare, cel mai eficient algoritm având o complexitate exponențială, referitor la numărul de cifre. Astfel, un experiment de factorizare a unui număr de 200 de cifre s-a terminat cu succes abia după mai multe luni. La experiment au fost folosite 80 de calculatoare cu procesor Opteron de 2,2 GHz, conectate într-o rețea de tip Gigabit.

Faptul că factorizarea numerelor mari este dificilă se folosește deseori în criptografie, și anume la crearea unor algoritmi pentru cifrare foarte sigură.

Exemple

$15=3\cdot 5$

$64=2^{6}$

Vezi și

• Paul Leyland