6.3.2. Нахсмвдение истинных сомножителей над целыми числами
Чтобы разложить полином 
из 
на множители, мы должны сделать следующее:
1. Выбрать подходящее простое число 
и разлагать 
над 
2. Выбрать минимальное значение k, такое, что
и поднять разложение 
над 
до разложения над 
. Значение k, определяемое этим соотношением, получено из 
, принимая во внимание факт, что мы ищем делители полинома 
(в соответствии с механизмом восстановления старшего коэффициента, как мы видели в рассуждениях разд. 6.3.1 после первого примера подъема) и что мы можем ограничиться делителями степени 
После получения разложения полинома 
работал с полиномами, которые не обязательно являются нормированными, мы должны сделать следующий шаг 3.
3. Вычислить полином 
над 
для каждого подмножества S множества 
такого, что 
и проверить, является ли 
делителем полинома 
Если да, то примитивная часть полинома 
является сомножителем полинома 
над целыми числами.
В настоящее время в общем случае не существует способа узнать, какое подмножество неприводимых сомножителей по модулю 
образует неприводимый сомножитель полинома 
над целыми числами, и, таким образом, нам нужно проверить для всех
возможных комбинаций степени 
дают ли они сомножитель полинома 
над Z. Если 
неприводим над Z, то ни одно из этих пробных делений не будет успешным, и, как мы уже упоминали, тест экспоненциально зависит от числа 
сомножителей по модулю 
Однако можно значительно уменьшить число пробных делений в 
если (1) сначала проверить делимость свободных членов, а затем (2) разложить 
по модулю нескольких простых чисел. На шагах 2 и 3 в приведенном выше алгоритме надо использовать простое число с наименьшим числом сомножителей и сочетать информацию о степенях сомножителей по модулю различных простых чисел, чтобы уменьшить разноообразие возможностей для степеней сомножителей над Z. Как мы уже видели, если 
разлагается по модулю 
на 3 сомножителя степени 2 и если 
разлагается по модулю 
на 2 сомножителя степени 3, то полином 
неприводим над целыми числами.
Наконец, существуют два очевидных способа реализации шага 3. Первый — это процедура мощности, т.е. перебираем сочетания по s сомножителей для 
Второй подход — это процедура степени, т.е. перебираем сочетания общей степени s для 
Обнаружено, что процедура мощности предпочтительнее.
