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.

${\displaystyle 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.^[1]

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

Exemple

${\displaystyle 15=3\cdot 5}$

${\displaystyle 64=2^{6}}$

Note

Vezi și

• Paul Leyland

Acest articol legat de matematică este deocamdată un ciot. Poți ajuta Wikipedia prin completarea lui.