Descompunerea în factori primi

De la Wikipedia, enciclopedia liberă
(Redirecționat de la Factorizarea întregilor)
Sari la navigare Sari la căutare

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

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ă.

Note[modificare | modificare sursă]

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

Vezi și[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]