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

  1. ^ Eric W. Weisstein (). „RSA-640 Factored”. Accesat în . 

Vezi și