Описание тега factorization

Факторизация - это разложение объекта (например, числа, многочлена или матрицы) на произведение других объектов или факторов, которые при умножении дают исходный. Например, число45 факторы как 3 × 15 или в простые числа как 3 × 3 × 5, а полином x^2 − 4 факторы как (x − 2)(x + 2). Во всех случаях получается продукт из более простых предметов.

Целью факторизации в полном объеме обычно является сокращение чего-либо до "базовых строительных блоков", например чисел до простых чисел или полиномов до неприводимых многочленов. Разложение целых чисел на множители покрывается основной теоремой арифметики, а разложение многочленов на множители - основной теоремой алгебры. Формулы Виэта связывают коэффициенты многочлена с его корнями.

Противоположностью полиномиальной факторизации является расширение, умножение полиномиальных множителей в "расширенный" полином, записанный как просто сумма членов.

Целочисленная факторизация для больших целых чисел кажется сложной проблемой. Не существует известного способа ее быстрого выполнения. Его сложность является основой предполагаемой безопасности некоторых алгоритмов криптографии с открытым ключом, таких как RSA.

Матрица также может быть факторизована в произведение матриц специальных типов для приложений, в которых такая форма удобна. Одним из основных примеров этого является использование ортогональной или унитарной матрицы и треугольной матрицы. Есть разные типы: QR-разложение, LQ, QL, RQ, RZ.

Другой пример - факторизация функции как композиции других функций, обладающих определенными свойствами; например, каждую функцию можно рассматривать как композицию сюръективной функции с инъективной функцией. Эта ситуация обобщается системами факторизации.