В математике , особенно в вычислительной алгебре , алгоритм Берлекампа является хорошо известным методом факторизации многочленов по конечным полям (также известным как поля Галуа ). Алгоритм состоит в основном из редукции матриц и вычислений полиномиального НОД . Он был изобретен Элвином Берлекампом в 1967 году. Он был доминирующим алгоритмом для решения проблемы до алгоритма Кантора – Цассенхауза в 1981 году. В настоящее время он реализован во многих хорошо известных системах компьютерной алгебры .
Обзор
Алгоритм Берлекампа принимает на вход полином без квадратов (т.е. без повторяющихся факторов) степени с коэффициентами в конечном поле и дает на выходе многочлен с коэффициентами в том же поле такими, что разделяет . Затем алгоритм может быть применен рекурсивно к этим и последующим делителям, пока мы не найдем разложениев степени неприводимых многочленов (напомним, что кольцо многочленов над конечным полем является единственной областью факторизации ).
Все возможные факторы содержатся в фактор-кольце
Алгоритм ориентирован на полиномы которые удовлетворяют сравнению:
Эти многочлены образуют подалгебру в R (которую можно рассматривать как-мерное векторное пространство над ), называемая подалгеброй Берлекампа . Подалгебра Берлекампа интересна тем, что многочлены он содержит удовлетворение
В общем, не каждый НОД в приведенном выше продукте будет нетривиальным фактором , но некоторые из них предоставляют факторы, которые мы ищем.
Алгоритм Берлекампа находит многочлены подходит для использования с вышеуказанным результатом, вычисляя базис для подалгебры Берлекампа. Это достигается за счет наблюдения, что подалгебра Берлекампа на самом деле является ядром некоторого матрица над , которая получается из так называемой матрицы Берлекампа многочлена, обозначаемой . Если тогда коэффициент при -й степенной член в сокращении по модулю , то есть:
С некоторым полиномом , сказать:
мы можем связать вектор-строку:
Относительно просто увидеть, что вектор-строка соответствует, таким же образом, уменьшению по модулю . Следовательно, многочлен находится в подалгебре Берлекампа тогда и только тогда, когда (где это единичная матрица ), то есть тогда и только тогда, когда она находится в нулевом пространстве.
Вычисляя матрицу и приведя его к сокращенной форме эшелона строк, а затем легко считывая базис для нулевого пространства, мы можем найти базис для подалгебры Берлекампа и, следовательно, построить многочленыв этом. Затем нам нужно последовательно вычислить НОД указанной выше формы, пока мы не найдем нетривиальный фактор. Поскольку кольцо многочленов над полем является евклидовой областью , мы можем вычислить эти НОД, используя алгоритм Евклида .
Концептуальное алгебраическое объяснение
С некоторой абстрактной алгеброй идея алгоритма Берлекампа становится концептуально ясной. Представим конечное поле, где для некоторого простого p, поскольку . Можно предположить, что является свободным от квадратов, взяв все возможные корни pth и затем вычислив НОД с его производной.
Теперь предположим, что - разложение на неприводимые. Тогда у нас есть изоморфизм колец,, задаваемый китайской теоремой об остатках. Ключевое наблюдение состоит в том, что автоморфизм Фробениуса ездит с , так что если обозначить , тогда ограничивается изоморфизмом . По теории конечного полявсегда является простым подполем этого расширения поля. Таким образом, имеет элементы тогда и только тогда, когда неприводимо.
Более того, мы можем использовать тот факт, что автоморфизм Фробениуса является -линейный для расчета фиксированного набора. То есть отметим, что это -подпространство, и явный базис для него может быть вычислен в кольце многочленов вычисляя и установив линейные уравнения на коэффициенты при многочлены, которые удовлетворяются тогда и только тогда, когда это фиксировано Фробениусом. Отметим, что на данный момент у нас есть эффективно вычислимый критерий неприводимости, и оставшийся анализ показывает, как использовать его для поиска факторов.
Теперь алгоритм разбивается на два случая:
- В случае малых мы можем построить любой , а затем заметьте, что для некоторых Существуют чтобы а также . Такой имеет общий нетривиальный фактор с , который можно вычислить с помощью gcd. В виде маленький, мы можем перебрать все возможные .
- В случае больших простых чисел, которые обязательно являются нечетными, можно использовать тот факт, что случайный ненулевой элемент из квадрат с вероятностью , и что карта отображает множество ненулевых квадратов в , а множество неквадратов к . Таким образом, если взять случайный элемент, то с хорошей вероятностью будет иметь нетривиальный фактор, общий с .
Для получения дополнительной информации можно проконсультироваться. [1]
Приложения
Одним из важных приложений алгоритма Берлекампа является вычисление дискретных логарифмов над конечными полями., где прост и . Вычисление дискретных логарифмов - важная проблема в криптографии с открытым ключом и кодировании с контролем ошибок . Для конечного поля самым быстрым известным методом является метод исчисления индексов , который включает факторизацию элементов поля. Если представить поле обычным способом - то есть как многочлены над базовым полем , приведенный по модулю неприводимого многочлена степени - тогда это просто полиномиальная факторизация, как это предусмотрено алгоритмом Берлекампа.
Реализация в системах компьютерной алгебры
Доступ к алгоритму Берлекампа можно получить в пакете PARI / GP с помощью команды factormod и на веб-сайте WolframAlpha [1] .
Смотрите также
Рекомендации
- ^ "Теория вычислений - Декстер Козен" . Springer . Проверено 19 сентября 2020 .
- Берлекамп, Элвин Р. (1967). "Факторизация многочленов по конечным полям". Технический журнал Bell System . 46 : 1853–1859. DOI : 10.1002 / j.1538-7305.1967.tb03174.x . MR 0219231 . BSTJ Позже переиздан в: Берлекамп, Элвин Р. (1968). Алгебраическая теория кодирования . Макгроу Хилл. ISBN 0-89412-063-8.
- Кнут, Дональд Э (1997). «4.6.2 Факторизация многочленов». Получисловые алгоритмы . Искусство программирования . 2 (Третье изд.). Ридинг, Массачусетс: Эддисон-Уэсли. С. 439–461, 678–691. ISBN 0-201-89684-2.