Читать онлайн «Компьютерная алгебра. Факторизация многочленов»

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им*. М. В. ЛОМОНОСОВА Механико-математический факультет КОМПЬЮТЕРНАЯ АЛГЕБРА Факторизация ммогочлено! Издательство Московского университета 1988 УДК 512. 622 Панкратьев Е. В. Компьютерная алгебра. Фак- Факторизация многочленов. - М. : Изд-во Моск. ун-та, 1988. - 85 С. ISBN 5-221-00591-0. Книга является первой в серии учебных посо- пособий по курсу "Компьютерная алгевра". Рассматри- Рассматривается одна из актуальных задач компьютерной ал- алгебры - разложение многочленов на неприводимые множители. В последние 20 лет получены значи- значительные результаты, позволяющие аффективно ис- использовать для решения этой задачи вычислитель- вычислительную технику. ' В посовии нашли отражение современ- современные алгоритмы факторизации и работы, проводимые на механико-математическом факультете по их ре- реализации. Для студентов механико-математического фа- факультета. Рецензенты докт. физ. -мат. наук В. Н. Лать канд. физ. мат. наук А. В. ОГЛАВЛЕНИЕ Введение 1. Алгоритм Кронекера t 2. Комбинаторные оценки 2. 1. Границы для коэффициентов делителя мно- многочлена 2. 2. Редуцированные Базисы решетки 3. Разложение на множители, свободные от квадра- квадратов 4. Выделение линейных множителей 5. Факторизация, основанная на переворе неприво- неприводимых сомножителей в KtxD 5. 1. Овщая схема 5. 2. Разложение многочленов на неприводимые множители по модулю р . 5. 3. Лемма Гензеля 5. 4. Обсуждение алгоритма 6. Алгоритмы факторизации, основанные на выворе малого вектора в решетке 6. 1. Общая схема факторизации 6. 2. Архимедова метрика 6. 3. Р-адическая метрика 7. Редуцирование Базиса в решетке 8. Замечания по реализации алгоритмов факториза- факторизации Литература - 3 - ВВЕДЕНИЕ Что такое компьютерная алreБра? Термин "компьютерная алгебра" появился в конце 70-х годов и длительное время употреблялся в качестве синонима терминов "аналитические и символьные вычисления на ЭВМ". Даже в настоящее время этот термин на французском языке дословно означает "формальные вычисления". В чем основные отличия символьных вычисле- вычислений от численных и почему возник термин "компь- "компьютерная алгебра"? Когда говорим о вычислительных методах, то считаем, что все вычисления, выполняются в поле вещественных или комплексных чисел. В действи- действительности же всякая программа для ЭВМ имеет дело только с конечным набором рациональных чисел, поскольку только такие числа представляются в компьютере. Для записи целого числа отводится обычно 16 или 32 двоичных символа' (бита), для вещественного - 32 или 64 бита. Это'множество не замкнуто относительно арифметических операций, что может выражаться в различных переполнениях, например, при умножении достаточно больших чисел или при делении на маленькое число.