Факторизація

Візуальна ілюстрація многочлена x² + cx + d = (x + a)(x + b) де a + b рівне c та a × b рівне d.

Факторизація або розклад на множники — це декомпозиція об'єкту (наприклад, числа, многочлена або матриці) у добуток інших об'єктів, або множників, які після перемноження дадуть вихідний об'єкт. Наприклад, число 15 розкладається на прості множники як 3 × 5, многочлен x² − 4 розкладається на множники як (x − 2)(x + 2). У всіх випадках, отримано добуток простіших об'єктів.

Метою факторизації є зазвичай звести щось до «базових будівельних блоків», наприклад, цілі числа до простих чисел чи многочлени до незвідних многочленів. Факторизація цілих чисел забезпечується основною теоремою арифметики і факторизація многочленів — основною теоремою алгебри. Теорема Вієта пов'язує коефіцієнти многочлена з його коренями.

Цілі числа

Згідно з основною теоремою арифметики, кожне додатне ціле число більше одиниці має єдиний розклад на прості множники. За допомогою алгоритмів факторизації цілих чисел, можна розкласти будь-яке ціле число на прості множники за допомогою повторного застосування цих алгоритмів. Проте для дуже великих чисел невідомо ефективних алгоритмів.