Faktorizáció, elmélet és gyakorlat

Abstract

A számelméletben az egész számok faktorizációja összetett számok kisebb egész számok szorzatává való felbontását jelenti. Ha ezek az egész számok mindegyike prím, akkor prímfaktorizációról beszélünk. Megkülönböztetünk általános célú – ahol a futási idő kizárólag a faktorizálni kívánt szám méretétől függ –, és speciális célú – a futási idejük a faktorizálni kívánt szám tulajdonságaitól vagy egy, az adott szám ismeretlen faktorától függ – faktorizációs algoritmust.