Глава 6. Разложение на множители полиномов над целыми числами

6.1. Введение и обоснования

Ясно, что самый простой способ нахождения множителей данного полинома — это алгебраически найти его корни и тогда (Читателю следует сейчас снова просмотреть разд. 3.2.3.) Однако, как мы убедимся в гл. 7, мы можем алгебраически найти корни полинома, только если его степень 4. Для полиномов, степень которых больше 4, мы должны применить другой подход.

Помимо чисто теоретического интереса разложение полиномов на множители имеет большое практическое значение (например, в теории кодирования). Ньютон в своей Arithmetica Universalis (1707 г.) формулирует метод нахождения линейных и квадратичных множителей полиномов с целыми коэффициентами. В 1793 г. метод Ньютона был обобщен астрономом Фридрихом фон Шубертом, показавшим, как находить все множители степени за конечное число шагов (Cantor, 1908; р. 136-137). Метод Шуберта примерно через 90 лет был заново открыт Л. Кронекером. Однако, как мы вскоре убедимся, метод Кронекера-Шуберта имеет экспоненциальную вычислительную сложность по времени и, следовательно, мало пригоден для практического применения.

Гораздо лучшие результаты получаются при использовании методов разложения «по модулю р» вместе с техникой подгема разложения «по модулю до разложения на множители над целыми числами. Этот подход проиллюстрирован на рис. 6.1.1.

Однако, несмотря на то что подход, показанный на рис. 6.1.1, работает почти во всех практических случаях очень хорошо, в худшем случае он также имеет экспоненциальную границу времени вычислений. Совсем недавно А. Ленстра, X. Ленстра мл. и Л. Ловас (или просто ) применили теорию решеток к задаче разложения на множители и получили метод разложения с полиномиальным

временем вычисления (Lenstra А.К., Lenstra H.W., Lovasz L., 1982); изложение -метода выходит, однако, за рамки этой книги; см. (Lenstra, 1981, 1982а; Панкратьев, 1988).