質因數分解演算法

人們已經設計出許多演算法來確定給定數字的質因數（這個過程稱為質因數分解）。 它們的複雜性和精巧程度各不相同。 為這個計算上“困難”的問題構建通用演算法非常困難，因此，關於問題中數字或其因數的任何額外資訊通常可以用來節省大量時間。

尋找因數的最簡單方法是所謂的“直接搜尋分解”（又名試除法）。 在這種方法中，使用試除法系統地測試所有可能的因數，以檢視它們是否真正整除給定的數字。 它僅對非常小的數字實用。

已知最快的完全證明的確定性演算法是Pollard-Strassen方法（Pomerance 1982；Hardy等人1990）。