Эта статья входит в число добротных статей

Метод Берлекэмпа

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Элвин Берлекэмп

Метод Берлекэмпа (также алгоритм Берлекэмпа — Рабина) — вероятностный метод нахождения корней многочленов над полем с полиномиальной сложностью. Метод был описан американским математиком Элвином Берлекэмпом в 1970 году в качестве побочного к алгоритму факторизации многочленов над конечными полями и позже (в 1979 году) был доработан Михаэлем Рабином для случая произвольных конечных полей[1][2]. Изначальная версия алгоритма, предложенная Берлекэмпом в 1967 году, не была полиномиальной[3][4]. Опубликованная в 1970 году на основе результатов Цассенхауза[en] версия алгоритма работала с большими значениями , в ней заглавный метод использовался в качестве вспомогательного[1]. На момент публикации метод был распространён в профессиональной среде, однако редко встречался в литературе[4].

История[править | править код]

Михаэль Ошер Рабин

Метод был предложен Элвином Берлекэмпом в его работе по факторизации многочленов над конечными полями[1]. В ней факторизация многочлена на неприводимые сомножители над полем сводится к нахождению корней некоторых других многочленов над полем . При этом в оригинальной работе отсутствовало доказательство корректности алгоритма[2]. Алгоритм был доработан и обобщён на случай произвольных конечных полей Михаэлем Рабином[2]. В 1986 году Рене Перальта описал похожий алгоритм[5], решающий задачу нахождения квадратного корня в поле [6], а в 2000 году метод Перальты был обобщён для решения кубических уравнений[7].

В алгоритме Берлекэмпа многочлен сперва представляется в виде произведения , где  — произведение многочленов степени . Затем факторизация каждого такого многочлена степени сводится к поиску корней нового многочлена степени . В статье, вводящей алгоритм факторизации, было также предложено три метода для поиска корней многочлена в поле Галуа . Первые два сводят нахождение корней в поле к поиску корней в поле . Третий метод, являющийся предметом данной статьи, решает задачу поиска корней в поле , что вместе с двумя другими решает задачу факторизации[1].

Версия алгоритма факторизации, предложенная Берлекэмпом в его первой работе в 1967 г.[3], работала за , где  — количество неприводимых сомножителей многочлена. Таким образом, алгоритм являлся неполиномиальным и был непрактичным в случае, когда простое число было достаточно большим. В 1969 г. эта проблема была решена Хансом Цассенхаузом[en], показавшим, как свести узкое место алгоритма к задаче поиска корней некоторого многочлена[4]. В 1970 г. статья Берлекэмпа была переиздана уже с учётом решений Цассенхауза[1].

В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида и доказал, что вероятность ошибки одной итерации алгоритма не превосходит [2], а в 1981 г. Михаэль Бен-Ор усилил эту оценку до , где  — количество различных корней многочлена [8]. Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Алгоритм Кантора — Цассенхауза[en] являются вероятностными. В 1981 году Поль Камьон[fr] показал[9], что такой алгоритм существует для любого наперёд заданного числа , однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым[10].

В первом издании второго тома «Искусства программирования» про получисленные алгоритмы Дональд Кнут пишет, что аналогичные процедуры факторизации были известны к 1960 г., однако редко встречались в открытом доступе[4]. Один из первых опубликованных примеров использования метода можно обнаружить в работе Голомба, Велша[en] и Хейлса[en] от 1959 года о факторизации трёхчленов над , где рассматривался частный случай [11].

Алгоритм[править | править код]

Постановка задачи[править | править код]

Пусть  — нечётное простое число. Рассмотрим многочлен над полем остатков по модулю . Необходимо найти все числа такие что для всех возможных [2][12].

Рандомизация[править | править код]

Пусть . Нахождение всех корней такого многочлена равносильно его разбиению на линейные множители. Чтобы найти такое разбиение, достаточно научиться разбивать многочлен на любые два множителя, а затем запускаться в них рекурсивно. Для этого вводится в рассмотрение многочлен , где  — случайное число из . Если такой многочлен можно представить в виде произведения , то в терминах исходного многочлена это значит, что , что даёт разбиение на множители исходного многочлена [1][12].

Классификация элементов [править | править код]

По критерию Эйлера для любого монома выполнено ровно одно из следующих свойств[1]:

  1. Одночлен равен , если ,
  2. Одночлен делит , если  — квадратичный вычет по модулю ,
  3. Одночлен делит , если  — квадратичный невычет по этому модулю.

Таким образом, если не делится на , что можно проверить отдельно, то равно произведению наибольших общих делителей и [12].

Метод Берлекэмпа[править | править код]

Написанное выше приводит к следующему алгоритму[1]:

  1. В явном виде вычисляются коэффициенты многочлена ,
  2. Вычисляются остатки от деления на последовательным возведением в квадрат и взятием остатка от ,
  3. Двоичным возведением в степень вычисляется остаток от деления на с использованием посчитанных на прошлом шаге многочленов,
  4. Если , то указанные выше дают нетривиальное разбиение на множители,
  5. В противном случае все корни являются вычетами или невычетами одновременно и стоит попробовать другое значения .

Если также делится на некоторый многочлен , не имеющий корней в , то при подсчёте с и будет получено разбиение бесквадратного многочлена на нетривиальные сомножители, поэтому алгоритм позволяет найти все корни любых многочленов над , а не только тех, которые разбиваются в произведение мономов[12].

Извлечение квадратного корня[править | править код]

Пусть нужно решить сравнение , решениями которого являются элементы и соответственно. Их нахождение эквивалентно факторизации многочлена над полем . В таком частном случае задача упрощается, так как для решения достаточно посчитать только . Для полученного многочлена будет верно ровно одно из утверждений:

  1. НОД равен , из чего следует, что и являются квадратичными невычетами одновременно,
  2. НОД равен , из чего следует, что оба числа являются квадратичными вычетами,
  3. НОД равен одночлену , из чего следует, что ровно одно число из двух является квадратичным вычетом.

В третьем случае полученный одночлен должен быть равен или , или . Это позволяет записать решение в виде [1].

Пример[править | править код]

Пусть нужно решить сравнение . Для этого нужно факторизовать . Рассмотрим возможные значения :

  1. Пусть . Тогда , откуда . Оба числа являются невычетами и нужно брать другое .
  1. Пусть . Тогда , откуда . Отсюда , значит и .

Проверка показывает, что действительно и .

Обоснование метода[править | править код]

Алгоритм находит разбиение на нетривиальные множители во всех случаях, за исключением тех, в которых все числа являются вычетами или невычетами одновременно. Согласно теории циклотомии[13], вероятность такого события для случая, когда сами одновременно являются вычетами или невычетами одновременно (то есть, когда не подходит для нашей процедуры), можно оценить как [8], где  — количество различных чисел среди [1]. Таким образом, вероятность ошибки алгоритма не превосходит .

Применение к факторизации многочленов[править | править код]

Основная статья: Алгоритм Берлекэмпа

Из теории конечных полей известно, что если степень неприводимого многочлена равна , то такой многочлен является делителем и не является делителем для .

Таким образом, последовательно рассматривая многочлены где и для , можно разбить многочлен на множители вида , где — это произведение всех неприводимых многочленов степени , которые делят многочлен . Зная степень , можно определить количество таких многочленов, равное . Пусть . Если рассмотреть многочлен , где , то порядок такого многочлена в поле должен делить число . Если не делится на , то многочлен делится на , но не на .

Исходя из этого Цассенхауз[en] предложил искать делители многочлена в виде , где — некоторый достаточно большой делитель , например, . В частном случае получается в точности метод Берлекэмпа как он описан выше[4].

Время работы[править | править код]

Поэтапно время работы одной итерации алгоритма можно оценить следующим образом, считая степень многочлена равной :

  1. Учитывая, что по формуле бинома Ньютона, переход от к делается за ,
  2. Произведение многочленов и взятие остатка от одного многочлена по модулю другого делается за , поэтому вычисление делается за ,
  3. Аналогично предыдущему пункту, двоичное возведение в степень делается за ,
  4. Взятие от двух многочленов по алгоритму Евклида делается за .

Таким образом, одна итерация алгоритма может быть произведена за арифметических операций с элементами , а нахождение всех корней многочлена требует в среднем [8]. В частном случае извлечения квадратного корня величина равна двум, поэтому время работы оценивается как на одну итерацию алгоритма[12].

Примечания[править | править код]

  1. 1 2 3 4 5 6 7 8 9 10 E. R. Berlekamp. Factoring polynomials over large finite fields (англ.) // Mathematics of Computation. — 1970. — Vol. 24, iss. 111. — P. 713–735. — ISSN 1088-6842 0025-5718, 1088-6842. — DOI:10.1090/S0025-5718-1970-0276200-X.
  2. 1 2 3 4 5 M. Rabin. Probabilistic Algorithms in Finite Fields // SIAM Journal on Computing. — 1980-05-01. — Т. 9, вып. 2. — С. 273–280. — ISSN 0097-5397. — DOI:10.1137/0209024.
  3. 1 2 E. R. Berlekamp. Factoring polynomials over finite fields // The Bell System Technical Journal. — 1967-10. — Т. 46, вып. 8. — С. 1853–1859. — ISSN 0005-8580. — DOI:10.1002/j.1538-7305.1967.tb03174.x.
  4. 1 2 3 4 5 Donald E Knuth. The art of computer programming. Vol. 2 Vol. 2. — 1998. — ISBN 9780201896848.
  5. Tsz-Wo Sze. On taking square roots without quadratic nonresidues over finite fields // Mathematics of Computation. — 2011-01-03. — Т. 80, вып. 275. — С. 1797–1811. — ISSN 1088-6842 0025-5718, 1088-6842. — DOI:10.1090/s0025-5718-2011-02419-1.
  6. R. Peralta. A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) // IEEE Transactions on Information Theory. — 1986-11. — Т. 32, вып. 6. — С. 846–847. — ISSN 0018-9448. — DOI:10.1109/TIT.1986.1057236.
  7. C Padró, G Sáez. Taking cube roots in Zm // Applied Mathematics Letters. — 2002-08. — Т. 15, вып. 6. — С. 703–708. — ISSN 0893-9659. — DOI:10.1016/s0893-9659(02)00031-9.
  8. 1 2 3 M. Ben-Or. Probabilistic algorithms in finite fields // 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981). — 1981-10. — С. 394–398. — DOI:10.1109/SFCS.1981.37.
  9. Paul Camion. A Deterministic Algorithm for Factorizing Polynomials of Fq [X] // Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics. — Elsevier, 1983. — С. 149–157. — ISBN 9780444865120.
  10. Bruno Grenet, Joris van der Hoeven, Grégoire Lecerf. Deterministic root finding over finite fields using Graeffe transforms // Applicable Algebra in Engineering, Communication and Computing. — 2015-12-12. — Т. 27, вып. 3. — С. 237–257. — ISSN 1432-0622 0938-1279, 1432-0622. — DOI:10.1007/s00200-015-0280-5.
  11. Golomb, S. W., Hales, A., Welch, L. R. On the factorization of trinomials over GF(2) // Technical Report. — Jet Propulsion Lab., California Inst. of Tech.; Pasadena, CA, United States, July 14, 1959.
  12. 1 2 3 4 5 Alfred J. Menezes, Ian F. Blake, XuHong Gao, Ronald C. Mullin, Scott A. Vanstone. Applications of Finite Fields. — Springer US, 1993. — (The Springer International Series in Engineering and Computer Science). — ISBN 9780792392828.
  13. Marshall Hall. Combinatorial Theory. — John Wiley & Sons, 1998-07-16. — 464 с. — ISBN 9780471315186.