Факторизація - розклад чисел на прості множники.
Можна виділити два основних типи - спеціалізовані й універсальні алгоритми розкладу на множники.
Один з найбільш потужних спеціалізованих алгоритмів розкладу на множники - метод еліптичних кривих (режим виправлення помилок), що був винайдений в 1985 році Х.Ленстром молодшим. Час виконання цього методу залежить від розміру головних множників n, і відповідно алгоритм має тенденцію знаходити спочатку маленькі множники. До розвитку RSA системи шифрування, найкращим універсальним алгоритмом розкладу на множники був алгоритм ланцюгового поділу. Цей алгоритм розкладу на множники був оснований на ідеї відносного використання основи множника штрихів та добутку, пов’язаного з набором лінійних рівнянь, його рішення в кінцевому рахунку вело до факторизації. Та ж ідея лежить в основі найкращих універсальних алгоритмів розкладу на множники, що використовуються сьогодні: квадратична сітка (QS) та сітка поля цифр (NFS). Обидва ці алгоритми можуть бути легко паралелізовані, щоб дозволити розклад на множники на розпаралелених мережах АРМ. Квадратична сітка (решето) була розроблена Карлом Померансом 1984р. В 1994 році вона була використана групою дослідників на чолі з А.Ленстром до 129-розрядного множника 429- розрядного добутку модуля RSA, що був викладений Мартином Гарднером у 1977р. Факторизація була виконана через 8 місяців приблизно на 1600 комп’ютерах у всьому світі.
Експерименти довели, що NFS є дійсно добрим алгоритмом для розкладу на множники чисел, що мають принаймні 120 десяткових цифр (400 бітів).
