Î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.
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
Vezi și Paul Leyland
Categorie:Teoria numerelor