Введение

(Математическое) разложение на произведение

В математике, факторизация (или факторизация, см. различия в английской орфографии) состоит в представлении числа или другого математического объекта в виде произведения нескольких факторов, обычно меньших или более простых объектов того же типа. Например, 3 × 5 является целочисленной факторизацией числа 15, а (x – 2)(x + 2) – полиномиальной факторизацией x^(2) – 4. Факторизация обычно не считается значимой в числовых системах, допускающих деление, таких как действительные или комплексные числа, поскольку любое число можно тривиально представить в виде произведения, когда отличный от нуля. Однако, осмысленную факторизацию рационального числа или рациональной функции можно получить, представив его в несократимом виде и отдельно факторизовав его числитель и знаменатель. Факторизация впервые была рассмотрена древнегреческими математиками в случае целых чисел. Они доказали основную теорему арифметики, которая утверждает, что каждое положительное целое число может быть разложено на произведение простых чисел, которые нельзя далее разложить на целые числа, большие 1. Более того, эта факторизация уникальна с точностью до порядка следования факторов. Хотя целочисленная факторизация является своего рода обратной операцией умножению, она значительно сложнее с алгоритмической точки зрения, что используется в криптосистеме RSA для реализации криптографии с открытым ключом. Факторизация многочленов также изучалась на протяжении веков. В элементарной алгебре, факторизация многочлена сводит задачу нахождения его корней к задаче нахождения корней факторов. Многочлены с коэффициентами в целых числах или в поле обладают свойством единственности факторизации, являющимся вариантом основной теоремы арифметики, в котором простые числа заменены на неприводимые многочлены. В частности, унивариантный многочлен с комплексными коэффициентами допускает единственную (с точностью до порядка) факторизацию на линейные многочлены: это вариант основной теоремы алгебры. В этом случае факторизация может быть выполнена с использованием алгоритмов поиска корней. Случай многочленов с целочисленными коэффициентами является фундаментальным для компьютерной алгебры. Существуют эффективные компьютерные алгоритмы для вычисления (полных) факторизаций в кольце многочленов с рациональными коэффициентами (см. факторизация многочленов). Коммутативное кольцо, обладающее свойством единственности факторизации, называется областью однозначной факторизации. Существуют системы чисел, такие как некоторые кольца алгебраических целых чисел, которые не являются областями однозначной факторизации. Однако кольца алгебраических целых удовлетворяют более слабому свойству областей Дедекинда: идеалы однозначно разлагаются на простые идеалы. Факторизация также может относиться к более общим разложениям математического объекта на произведение меньших или более простых объектов. Например, любую функцию можно представить в виде композиции сюръективной функции и инъективной функции. Матрицы обладают множеством видов матричных разложений. Например, каждая матрица имеет единственное LUP-разложение в виде произведения нижней треугольной матрицы L со всеми диагональными элементами, равными единице, верхней треугольной матрицы U и матрицы перестановок P; это матричная формулировка метода Гаусса.

Целые числа

Согласно основной теореме арифметики, каждое целое число, большее 1, имеет уникальное (с точностью до порядка сомножителей) разложение на простые числа, то есть на такие целые числа, которые нельзя разложить на произведение целых чисел, больших единицы. Для вычисления разложения целого числа n требуется алгоритм для нахождения делителя q числа n или для определения того, что n является простым числом. Когда такой делитель найден, повторное применение этого алгоритма к сомножителям q и n / q в конечном итоге дает полное разложение n на множители.

Для нахождения делителя q числа n, если он существует, достаточно проверить все значения q, такие что 1 < q и q² ≤ n. Действительно, если r является делителем n, причём r² > n, то q = n / r является делителем n, для которого q² ≤ n.

Если проверять значения q в возрастающем порядке, то первый найденный делитель обязательно является простым числом, а кофактор r = n / q не может иметь делителей, меньших q. Для получения полного разложения на множители достаточно продолжить алгоритм, находя делитель r, который не меньше q и не больше. Нет необходимости проверять все значения q для применения этого метода. В принципе, достаточно проверять только простые делители. Для этого нужна таблица простых чисел, которую можно сгенерировать, например, с помощью решета Эратосфена. Поскольку метод разложения на множители по сути выполняет ту же работу, что и решето Эратосфена, обычно эффективнее проверять на делимость только те числа, для которых не очевидно, являются ли они простыми или нет. Как правило, можно начать с проверки 2, 3, 5 и чисел больше 5, у которых последняя цифра равна 1, 3, 7 или 9, а сумма цифр не кратна 3. Этот метод хорошо работает для разложения на множители небольших целых чисел, но неэффективен для больших чисел. Например, Пьеру де Ферма не удалось установить, что шестое число Ферма не является простым числом. На самом деле, применение вышеописанного метода потребовало бы более 10 000 операций для числа, состоящего из 10 десятичных цифр. Существуют более эффективные алгоритмы факторизации. Однако они остаются относительно неэффективными, поскольку даже с использованием самых мощных компьютеров невозможно разложить на множители число, состоящее из 500 десятичных цифр, которое является произведением двух случайно выбранных простых чисел. Это обеспечивает безопасность криптосистемы RSA, широко используемой для безопасной интернет-коммуникации.

История разбивки выражений на множители

Систематическое использование алгебраических преобразований для упрощения выражений (в особенности уравнений) можно отнести к IX веку, к книге аль-Хорезми "Краткая книга об исчислении завершением и уравновешиванием", название которой отражает два типа таких преобразований. Однако даже для решения квадратных уравнений метод разложения на множители не использовался до работ Харриота, опубликованных в 1631 году, спустя десять лет после его смерти. В своей книге "Практика аналитического искусства для решения алгебраических уравнений" Харриот составил таблицы для сложения, вычитания, умножения и деления мономов, биномов и триномов. Затем, во втором разделе, он представил уравнение 1 = aa − ba + ca = + bc и показал, что оно соответствует форме умножения, которую он ранее привел, получив разложение на множители (a − b)(a + c).

Общие методы

Следующие методы применимы к любому выражению, являющемуся суммой, или которое можно привести к виду суммы. Следовательно, они чаще всего используются для полиномов, однако могут быть применены и в случаях, когда слагаемые суммы не являются мономами, то есть представляют собой произведение переменных и констант.

Факторизация примитивных частей и содержания

Каждый многочлен с рациональными коэффициентами может быть однозначно разложен на произведение рационального числа и многочлена с целыми коэффициентами, который является примитивным (то есть наибольший общий делитель его коэффициентов равен 1) и имеет положительный старший коэффициент (коэффициент при старшей степени). Например:

В этом разложении рациональное число называется содержанием, а примитивный многочлен – примитивной частью. Вычисление этого разложения можно выполнить следующим образом: сначала приведите все коэффициенты к общему знаменателю, чтобы получить частное от деления на целое число q многочлена с целыми коэффициентами. Затем выделите наибольший общий делитель p коэффициентов этого многочлена, чтобы получить примитивную часть, а само q будет содержанием. Наконец, при необходимости измените знаки p и всех коэффициентов примитивной части. Это разложение может привести к результату, который больше исходного многочлена (особенно когда имеется много взаимно простых знаменателей), но даже в этом случае примитивная часть, как правило, удобнее для дальнейшего разложения на множители.

Уникальные области факторизации

Целые числа и многочлены над полем обладают свойством однозначной факторизации, то есть каждый ненулевой элемент может быть разложен в произведение обратимого элемента (единицы, ±1 в случае целых чисел) и произведение неприводимых элементов (простых чисел в случае целых чисел), и эта факторизация уникальна с точностью до перестановки сомножителей и переноса единиц между ними. Интегральные области, обладающие этим свойством, называются областями однозначной факторизации (UFD). Наибольшие общие делители существуют в UFD, и, наоборот, любая интегральная область, в которой существуют наибольшие общие делители, является UFD. Каждая область главных идеалов является UFD. Евклидова область — это интегральная область, в которой определено евклидово деление, аналогичное делению целых чисел. Каждая евклидова область является областью главных идеалов и, следовательно, UFD. В евклидовой области евклидово деление позволяет определить алгоритм Евклида для вычисления наибольших общих делителей. Однако это не подразумевает существование алгоритма факторизации. Существует явный пример поля F, для которого не может существовать никакого алгоритма факторизации в евклидовой области F[x] одно переменных многочленов над F.

Идеалы

В алгебраической теории чисел изучение диофантовых уравнений привело математиков в XIX веке к введению обобщений целых чисел, называемых алгебраическими целыми. Первыми кольцами алгебраических целых чисел, которые были рассмотрены, были гауссовы целые и айзенштейновские целые, которые, как и обычные целые числа, обладают свойством быть областями главных идеалов и, следовательно, имеют свойство однозначной факторизации. К сожалению, вскоре стало ясно, что большинство колец алгебраических целых чисел не являются областями главных идеалов и не имеют однозначной факторизации. Простейший пример – в котором

и все эти множители являются неприводимыми. Отсутствие однозначной факторизации является серьезным препятствием для решения диофантовых уравнений. Например, многие ошибочные доказательства последней теоремы Ферма (вероятно, включая "истинно чудесное доказательство этого, которое слишком велико для этой страницы") основывались на неявном предположении об однозначной факторизации. Эта трудность была разрешена Дедекиндом, который доказал, что кольца алгебраических целых чисел имеют однозначную факторизацию идеалов: в этих кольцах каждый идеал является произведением простых идеалов, и эта факторизация однозначна с точностью до порядка множителей. Интегральные области, обладающие этим свойством однозначной факторизации идеалов, теперь называются дедекиндовыми областями. Они обладают множеством полезных свойств, которые делают их фундаментальными в алгебраической теории чисел.

Матрицы

Матричные кольца некоммутативны и не обладают свойством однозначной факторизации: как правило, существует множество способов представить матрицу в виде произведения матриц. Таким образом, задача факторизации заключается в поиске факторов заданного типа. Например, LU-разложение представляет матрицу в виде произведения нижней треугольной матрицы и верхней треугольной матрицы. Поскольку это не всегда возможно, обычно рассматривают "LUP-разложение", которое включает в себя матрицу перестановок в качестве третьего множителя. Подробную информацию о наиболее распространенных типах матричных разложений можно найти в статье "Разложение матриц". Логическая матрица представляет собой бинарное отношение, а умножение матриц соответствует композиции отношений. Факторизация отношения позволяет выявить его свойства, например, диффункциональное отношение.