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

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

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

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

Цілі числа

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

Див. також

• Факторизація графа
• Факторизація многочленів

Джерела

• Завало С. Т. (1974). Алгебра і теорія чисел. Київ: Вища школа. с. 399. (укр.) — 464 с.
• Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)