§ 32. Разложение на множители в конечное число шагов
Мы рассмотрели теоретическую возможность разложения каждого многочлена кольца 
над полем 2 на простые множители и в некоторых случаях указали средство выяснения того, возможно такое разложение или нет. Однако у нас нет метода, который позволял бы в любом случае решить вопрос о разложении многочлена в конечное число шагов Один из этих методов, который пригоден по крайней мере в случае, когда 
— поле рациональных чисел, мы сейчас изложим.
Согласно § 30 любой многочлен с рациональными коэффициентами можно считать многочленом с целыми коэффициентами и искать целочисленное разложение последнего. В кольце 
целых чисел разложение на простые множители проводится, очевидно, с помощью конечного числа проб; кроме того, в этом кольце есть лишь конечное множество обратимых элементов (+1 и -1), а потому лишь конечное число возможных разложений. В кольце многочленов 
число обратимых элементов тоже конечно: эти элементы суть 4-1 и —1. Индукцией по числу переменных 
все сводится к следующей задаче:
Пусть в кольце 
разложение на множители осуществляется в конечное число шагов, и пусть в 
существует лишь конечное множество обратимых элементов. Найти метод разложения произвольного многочлена 
кольца 
на простые множители.
Решение этой задачи было дано Кронекером.
Пусть 
многочлен 
степени из Если 
разложим, то один из сомножителей будет иметь степень 
следовательно, если 
наибольшее целое число, не превосходящее 
то мы должны проверить, имеет ли 
какой-либо делитель 
степени 
Найдем значения 
многочлена 
произвольно выбранных целочисленных точках 
Если теперь 
делится на 
то обязательно 
делится на 
делится на 
Но так как каждое целое число 
в кольце 
имеет лишь конечное число делителей, для 
имеется лишь конечное число возможных значений, которые, согласно условию, можно перебрать. Согласно теоремам из § 29 для каждой возможной комбинации значений 
существует ровно один многочлен 
причем 
всегда может быть указан в явном виде. Тем самым мы нашли конечное множество многочленов 
которые могут быть делителями данного многочлена. По поводу каждого конкретного многочлена 
с помощью алгоритма деления можно выяснить, является ли он в действительности делителем многочлена 
или нет. Если ни один из многочленов 
не окажется делителем многочлена 
(мы опускаем случаи обратимых делителей), то 
неразложим; в противном же случае находим некоторое разложение и к каждому из полученных множителей можно применить ту же процедуру и т. д.
В целочисленном случае 
описанный метод можно сильно сократить. Сначала нужно рассмотреть разложение данного многочлена по модулю 2 и, возможно, по модулю 3, чтобы понять, какие степени могли бы иметь его делители 
и каковы классы вычетов коэффициентов по модулю 2 и по модулю 3. Такие наблюдения значительно сократят число возможных претендентов на роль делителей вида 
Затем, применяя интерполяционную формулу Ньютона, можно заметить, что последний коэффициент 
какого бы то ни было делителя является старшим коэффициентом многочлена 
а это вновь уменьшает число возможностей. Наконец, часто используется прием, при котором берется более 
точек 
Здесь нужно определить возможные значения 
делящие те 
которые содержат наименьшее число простых делителей; остальные точки также можно использовать для того, чтобы ограничить число возможностей. Для этого при вычислении каждого многочлена 
нужно сначала выяснить, являются ли его значения в неучтенных еще точках а; делителями соответствующих чисел 
или нет.
(см. скан)
