Оглавление
- 1 Разложение многочленов на множители по конечным полям
- 1.1 Факторизация многочленов
- 1.2 Конечные поля
- 1.3 Неприводимые многочлены
- 1.4 Пример
- 1.5 Сложность алгоритмов
- 1.6 Алгоритмы факторинга
- 1.7 Бесквадратная факторизация
- 1.8 Разложение на множители различной степени
- 1.9 Алгоритм Кантора–Зассенхауса
- 1.10 Алгоритм Шоупа
- 1.11 Критерий несводимости Рабина
- 1.12 Описание книги
- 1.13 Оформление и идентификаторы
- 1.14 Оформление и цвета
- 1.15 Библиографическое описание
- 1.16 Примеры внешних ссылок
- 1.17 Полный текст статьи:
- 2 Факторизация полиномов по конечным полям – Arc.Ask3.Ru
Разложение многочленов на множители по конечным полям
-
Факторизация многочленов
- Разложение многочлена на произведение неприводимых множителей
- Теоретически возможно для многочленов с коэффициентами в любом поле
- На практике алгоритмы разработаны для конечных полей
-
Конечные поля
- Теория конечных полей важна в различных областях математики и информатики
- Конечное поле имеет конечный порядок, который всегда является простым числом или степенью простого числа
- Неприводимые многочлены позволяют строить конечные поля не простого порядка
-
Неприводимые многочлены
- Многочлен f в F[x] называется неприводимым, если он не является произведением двух многочленов положительной степени
- Неприводимые многочлены полезны для генераторов псевдослучайных чисел
-
Пример
- Многочлен P = x4 + 1 неприводим к Q, но не к конечному полю
- В любом расширении поля F2, P = (x + 1)4
-
Сложность алгоритмов
- Алгоритмы полиномиального разложения используют базовые полиномиальные операции
- Умножение двух многочленов степени не более n требует O(n2) операций
- Евклидово деление и полиномиальный наибольший общий делитель также требуют O(n2) операций
-
Алгоритмы факторинга
- Алгоритмы включают бесквадратную факторизацию, разложение на множители различной степени и факторизацию равной степени
- Алгоритм Берлекампа сочетает этапы 2 и 3, но применим только для небольших конечных полей
-
Бесквадратная факторизация
- Алгоритм определяет бесквадратную факторизацию для многочленов с коэффициентами из конечного поля Fq
- Использует производную и gcd многочлена и его производной
- Работает также над полем с нулевой характеристикой
-
Разложение на множители различной степени
- Алгоритм разбивает бесквадратный многочлен на произведение многочленов с одинаковой степенью
- Корректность основана на лемме о произведении всех монических неприводимых многочленов степени, делящей i
-
Алгоритм Кантора–Зассенхауса
- Вероятностный алгоритм для факторизации одномерных многочленов над конечными полями
- Требует нечетного порядка поля коэффициентов
- Среднее число итераций цикла while меньше 2.5 log2 r
- Сложность O(dn2 log(r) log(q))
-
Алгоритм Шоупа
- Детерминированный алгоритм для факторизации многочленов над простыми полями
- Временная сложность зависит от фактора p
- Средняя временная сложность полиномиальна в d log(p)
-
Критерий несводимости Рабина
- Основан на лемме о неприводимости многочленов
- Проверяет, что каждое значение d не превышает половины степени входного многочлена
- Сложность O(n2(n + log q)) или O(n2 log n log q) в зависимости от используемой арифметики
-
Описание книги
- Алгоритмы для компьютерной алгебры
- Автор: Kluwer Academic Publishers
- Бостон, Массачусетс
- Стр. xxii+585
-
Оформление и идентификаторы
- Идентификаторы для различных типов блокировок
- Идентификаторы для различных типов подписок
- Идентификаторы для различных типов корпусов
-
Оформление и цвета
- Различные цвета и размеры шрифтов
- Различные стили и цвета для различных элементов
-
Библиографическое описание
- ISBN: 0-7923-9259-0
- Ссылки на внешние ресурсы
-
Примеры внешних ссылок
- Некоторые неприводимые многочлены
- Теория поля и Галуа
- Поле Галуа
- Разложение многочленов на множители над конечными полями