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.
- , 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
Note
- ^ Eric W. Weisstein (). „RSA-640 Factored”. Accesat în .
Vezi și
- Paul Leyland
![]() | Acest articol legat de matematică este deocamdată un ciot. Poți ajuta Wikipedia prin completarea lui. |