Алгоритм Берлекэмпа — Рабина

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Элвин Берлекэмп

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

История

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

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

В алгоритме Берлекэмпа многочлен [math]\displaystyle{ f(x) = a_0 + a_1 x + \dots + a_n x^n }[/math] сперва представляется в виде произведения [math]\displaystyle{ f(x)=h_1(x)h_2(x) \dots h_n(x) }[/math], где [math]\displaystyle{ h_i }[/math] — произведение [math]\displaystyle{ r_i }[/math] многочленов степени [math]\displaystyle{ i }[/math]. Затем факторизация каждого такого многочлена [math]\displaystyle{ h_i(x) }[/math] степени [math]\displaystyle{ ir_i }[/math] сводится к поиску корней нового многочлена [math]\displaystyle{ H(x) }[/math] степени [math]\displaystyle{ r_i }[/math]. В статье, вводящей алгоритм факторизации, было также предложено три метода для поиска корней многочлена в поле Галуа [math]\displaystyle{ \mathbb F_{p^k} }[/math]. Первые два сводят нахождение корней в поле [math]\displaystyle{ \mathbb F_{p^k} }[/math] к поиску корней в поле [math]\displaystyle{ \mathbb F_p }[/math]. Третий метод, являющийся предметом данной статьи, решает задачу поиска корней в поле [math]\displaystyle{ \mathbb F_p }[/math], что вместе с двумя другими решает задачу факторизации[1].

Версия алгоритма факторизации, предложенная Берлекэмпом в его первой работе в 1967 г.[3], работала за [math]\displaystyle{ O(n^3+prn) }[/math], где [math]\displaystyle{ r }[/math] — количество неприводимых сомножителей многочлена. Таким образом, алгоритм являлся неполиномиальным и был непрактичным в случае, когда простое число [math]\displaystyle{ p }[/math] было достаточно большим. В 1969 г. эта проблема была решена Хансом Цассенхаузом[en], показавшим, как свести узкое место алгоритма к задаче поиска корней некоторого многочлена[4]. В 1970 г. статья Берлекэмпа была переиздана уже с учётом решений Цассенхауза[1].

В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида [math]\displaystyle{ \mathbb F_{p^k} }[/math] и доказал, что вероятность ошибки одной итерации алгоритма не превосходит [math]\displaystyle{ 1/2 }[/math][2], а в 1981 г. Михаэль Бен-Ор усилил эту оценку до [math]\displaystyle{ 1-1/2^{k-1}+O\left(1/\sqrt{p}\right) }[/math], где [math]\displaystyle{ k }[/math] — количество различных корней многочлена [math]\displaystyle{ f(x) }[/math][8]. Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Алгоритм Кантора — Цассенхауза[en] являются вероятностными. В 1981 году Поль Камьон[fr] показал[9], что такой алгоритм существует для любого наперёд заданного числа [math]\displaystyle{ p }[/math], однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым[10].

В первом издании второго тома «Искусства программирования» про получисленные алгоритмы Дональд Кнут пишет, что аналогичные процедуры факторизации были известны к 1960 г., однако редко встречались в открытом доступе[4]. Один из первых опубликованных примеров использования метода можно обнаружить в работе Голомба, Велша[en] и Хейлса[en] от 1959 года о факторизации трёхчленов над [math]\displaystyle{ \mathbb F_2 }[/math], где рассматривался частный случай [math]\displaystyle{ p=2,z=1 }[/math][11].

Алгоритм

Постановка задачи

Пусть [math]\displaystyle{ p }[/math] — нечётное простое число. Рассмотрим многочлен [math]\displaystyle{ f(x) = a_0 + a_1 x + \dots + a_n x^n }[/math] над полем [math]\displaystyle{ \mathbb Z_p }[/math] остатков по модулю [math]\displaystyle{ p }[/math]. Необходимо найти все числа [math]\displaystyle{ \lambda_1, \dots, \lambda_k }[/math] такие что [math]\displaystyle{ f(\lambda_i)\equiv 0 \pmod p }[/math] для всех возможных [math]\displaystyle{ i }[/math][2][12].

Рандомизация

Пусть [math]\displaystyle{ f(x) = (x-\lambda_1)(x-\lambda_2)\dots(x-\lambda_n) }[/math]. Нахождение всех корней такого многочлена равносильно его разбиению на линейные множители. Чтобы найти такое разбиение, достаточно научиться разбивать многочлен на любые два множителя, а затем запускаться в них рекурсивно. Для этого вводится в рассмотрение многочлен [math]\displaystyle{ f_z(x)=f(x-z) = (x-\lambda_1 - z)(x-\lambda_2 - z) \dots (x-\lambda_n-z) }[/math], где [math]\displaystyle{ z }[/math] — случайное число из [math]\displaystyle{ \mathbb Z_p }[/math]. Если такой многочлен можно представить в виде произведения [math]\displaystyle{ f_z(x)=p_0(x)p_1(x) }[/math], то в терминах исходного многочлена это значит, что [math]\displaystyle{ f(x) =p_0(x+z)p_1(x+z) }[/math], что даёт разбиение на множители исходного многочлена [math]\displaystyle{ f(x) }[/math][1][12].

Классификация элементов [math]\displaystyle{ \mathbb F_p }[/math]

По критерию Эйлера для любого монома [math]\displaystyle{ (x-\lambda) }[/math] выполнено ровно одно из следующих свойств[1]:

  1. Одночлен равен [math]\displaystyle{ x }[/math], если [math]\displaystyle{ \lambda = 0 }[/math],
  2. Одночлен делит [math]\displaystyle{ g_0(x)=(x^{(p-1)/2}-1) }[/math], если [math]\displaystyle{ \lambda }[/math] — квадратичный вычет по модулю [math]\displaystyle{ p }[/math],
  3. Одночлен делит [math]\displaystyle{ g_1(x)=(x^{(p-1)/2}+1) }[/math], если [math]\displaystyle{ \lambda }[/math] — квадратичный невычет по этому модулю.

Таким образом, если [math]\displaystyle{ f_z(x) }[/math] не делится на [math]\displaystyle{ x }[/math], что можно проверить отдельно, то [math]\displaystyle{ f_z(x) }[/math] равно произведению наибольших общих делителей [math]\displaystyle{ \gcd(f_z(x);g_0(x)) }[/math] и [math]\displaystyle{ \gcd(f_z(x);g_1(x)) }[/math][12].

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

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

  1. В явном виде вычисляются коэффициенты многочлена [math]\displaystyle{ f_z(x) = f(x-z) }[/math],
  2. Вычисляются остатки от деления [math]\displaystyle{ x,x^2, x^{2^2},x^{2^3}, x^{2^4}, \dots, x^{2^{\lfloor \log_2 p \rfloor}} }[/math] на [math]\displaystyle{ f_z(x) }[/math] последовательным возведением в квадрат и взятием остатка от [math]\displaystyle{ f_z(x) }[/math],
  3. Двоичным возведением в степень вычисляется остаток от деления [math]\displaystyle{ x^{(p-1)/2} }[/math] на [math]\displaystyle{ f_z(x) }[/math] с использованием посчитанных на прошлом шаге многочленов,
  4. Если [math]\displaystyle{ x^{(p-1)/2} \not \equiv \pm 1 \pmod{f_z(x)} }[/math], то указанные выше [math]\displaystyle{ \gcd }[/math] дают нетривиальное разбиение [math]\displaystyle{ f_z(x) }[/math] на множители,
  5. В противном случае все корни [math]\displaystyle{ f_z(x) }[/math] являются вычетами или невычетами одновременно и стоит попробовать другое значения [math]\displaystyle{ z }[/math].

Если [math]\displaystyle{ f(x) }[/math] также делится на некоторый многочлен [math]\displaystyle{ g(x) }[/math], не имеющий корней в [math]\displaystyle{ \mathbb Z_p }[/math], то при подсчёте [math]\displaystyle{ \gcd }[/math] с [math]\displaystyle{ g_0(x) }[/math] и [math]\displaystyle{ g_1(x) }[/math] будет получено разбиение бесквадратного многочлена [math]\displaystyle{ f_z(x)/g_z(x) }[/math] на нетривиальные сомножители, поэтому алгоритм позволяет найти все корни любых многочленов над [math]\displaystyle{ \mathbb Z_p }[/math], а не только тех, которые разбиваются в произведение мономов[12].

Извлечение квадратного корня

Пусть нужно решить сравнение [math]\displaystyle{ x^2 \equiv a \pmod{p} }[/math], решениями которого являются элементы [math]\displaystyle{ \beta }[/math] и [math]\displaystyle{ -\beta }[/math] соответственно. Их нахождение эквивалентно факторизации многочлена [math]\displaystyle{ f(x) = x^2-a=(x-\beta)(x+\beta) }[/math] над полем [math]\displaystyle{ \mathbb Z_p }[/math]. В таком частном случае задача упрощается, так как для решения достаточно посчитать только [math]\displaystyle{ \gcd(f_z(x); g_0(x)) }[/math]. Для полученного многочлена будет верно ровно одно из утверждений:

  1. НОД равен [math]\displaystyle{ 1 }[/math], из чего следует, что [math]\displaystyle{ z+\beta }[/math] и [math]\displaystyle{ z-\beta }[/math] являются квадратичными невычетами одновременно,
  2. НОД равен [math]\displaystyle{ f_z(x) }[/math], из чего следует, что оба числа являются квадратичными вычетами,
  3. НОД равен одночлену [math]\displaystyle{ (x-t) }[/math], из чего следует, что ровно одно число из двух является квадратичным вычетом.

В третьем случае полученный одночлен должен быть равен или [math]\displaystyle{ (x-z-\beta) }[/math], или [math]\displaystyle{ (x-z+\beta) }[/math]. Это позволяет записать решение в виде [math]\displaystyle{ \beta = (t - z) \pmod{p} }[/math][1].

Пример

Пусть нужно решить сравнение [math]\displaystyle{ x^2 \equiv 5\pmod{11} }[/math]. Для этого нужно факторизовать [math]\displaystyle{ f(x)=x^2-5=(x-\beta)(x+\beta) }[/math]. Рассмотрим возможные значения [math]\displaystyle{ z }[/math]:

  1. Пусть [math]\displaystyle{ z=3 }[/math]. Тогда [math]\displaystyle{ f_z(x) = (x-3)^2 - 5 = x^2 - 6x + 4 }[/math], откуда [math]\displaystyle{ \gcd(x^2 - 6x + 4 ; x^5 - 1) = 1 }[/math]. Оба числа [math]\displaystyle{ 3 \pm \beta }[/math] являются невычетами и нужно брать другое [math]\displaystyle{ z }[/math].
  1. Пусть [math]\displaystyle{ z=2 }[/math]. Тогда [math]\displaystyle{ f_z(x) = (x-2)^2 - 5 = x^2 - 4x - 1 }[/math], откуда [math]\displaystyle{ \gcd( x^2 - 4x - 1 ; x^5 - 1)\equiv x - 9 \pmod{11} }[/math]. Отсюда [math]\displaystyle{ x - 9 = x - 2 - \beta }[/math], значит [math]\displaystyle{ \beta \equiv 7 \pmod{11} }[/math] и [math]\displaystyle{ -\beta \equiv -7 \equiv 4 \pmod{11} }[/math].

Проверка показывает, что действительно [math]\displaystyle{ 7^2 \equiv 49 \equiv 5\pmod{11} }[/math] и [math]\displaystyle{ 4^2\equiv 16 \equiv 5\pmod{11} }[/math].

Обоснование метода

Алгоритм находит разбиение [math]\displaystyle{ f_z(x) }[/math] на нетривиальные множители во всех случаях, за исключением тех, в которых все числа [math]\displaystyle{ z+\lambda_1, z+\lambda_2, \dots, z+\lambda_n }[/math] являются вычетами или невычетами одновременно. Согласно теории циклотомии[1], вероятность такого события для случая, когда [math]\displaystyle{ \lambda_1, \dots, \lambda_n }[/math] сами одновременно являются вычетами или невычетами одновременно (то есть, когда [math]\displaystyle{ z=0 }[/math] не подходит для нашей процедуры), можно оценить как [math]\displaystyle{ 1/2^{k-1} }[/math][8], где [math]\displaystyle{ k }[/math] — количество различных чисел среди [math]\displaystyle{ \lambda_1, \dots, \lambda_n }[/math][1]. Таким образом, вероятность ошибки алгоритма не превосходит [math]\displaystyle{ 1/2 }[/math].

Применение к факторизации многочленов

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

Из теории конечных полей известно, что если степень неприводимого многочлена [math]\displaystyle{ q(x) }[/math] равна [math]\displaystyle{ d }[/math], то такой многочлен является делителем [math]\displaystyle{ x^{p^d}-x }[/math] и не является делителем [math]\displaystyle{ x^{p^t}-x }[/math] для [math]\displaystyle{ t \lt d }[/math].

Таким образом, последовательно рассматривая многочлены [math]\displaystyle{ h_i(x) = \gcd(f_i(x), x^{p^i}-1) }[/math] где [math]\displaystyle{ f_1(x)=f(x) }[/math] и [math]\displaystyle{ f_i(x) = f_{i-1}(x) / h_{i-1}(x) }[/math] для [math]\displaystyle{ i\gt 1 }[/math], можно разбить многочлен [math]\displaystyle{ f(x) }[/math] на множители вида [math]\displaystyle{ f(x) = h_1(x) \dots h_n(x) }[/math], где [math]\displaystyle{ h_i(x) }[/math] — это произведение всех неприводимых многочленов степени [math]\displaystyle{ i }[/math], которые делят многочлен [math]\displaystyle{ f(x) }[/math]. Зная степень [math]\displaystyle{ h_i(x) }[/math], можно определить количество таких многочленов, равное [math]\displaystyle{ r_i=\deg h_i(x) / i }[/math]. Пусть [math]\displaystyle{ h_i(x) = p_1(x) \dots p_{r_i}(x) }[/math]. Если рассмотреть многочлен [math]\displaystyle{ p_j(x-z) }[/math], где [math]\displaystyle{ z \in \mathbb F_p }[/math], то порядок такого многочлена [math]\displaystyle{ d_j }[/math] в поле [math]\displaystyle{ \mathbb F_{p^i} }[/math] должен делить число [math]\displaystyle{ p^i-1 }[/math]. Если [math]\displaystyle{ d_j }[/math] не делится на [math]\displaystyle{ d_k }[/math], то многочлен [math]\displaystyle{ x^{d_j}-x }[/math] делится на [math]\displaystyle{ p_j(x-z) }[/math], но не на [math]\displaystyle{ p_k(x-z) }[/math].

Исходя из этого Цассенхауз[en] предложил искать делители многочлена [math]\displaystyle{ h_i(x-z) }[/math] в виде [math]\displaystyle{ \gcd(h_i(x-z), x^f-1) }[/math], где [math]\displaystyle{ f }[/math] — некоторый достаточно большой делитель [math]\displaystyle{ p^i-1 }[/math], например, [math]\displaystyle{ f=\frac{p^i-1}{2} }[/math]. В частном случае [math]\displaystyle{ i=1 }[/math] получается в точности метод Берлекэмпа как он описан выше[4].

Время работы

Поэтапно время работы одной итерации алгоритма можно оценить следующим образом, считая степень многочлена равной [math]\displaystyle{ n }[/math]:

  1. Учитывая, что [math]\displaystyle{ (x-z)^k = \sum\limits_{i=0}^k \binom{k}{i} (-z)^{k-i}x^i }[/math] по формуле бинома Ньютона, переход от [math]\displaystyle{ f(x) }[/math] к [math]\displaystyle{ f(x-z) }[/math] делается за [math]\displaystyle{ O(n^2) }[/math],
  2. Произведение многочленов и взятие остатка от одного многочлена по модулю другого делается за [math]\displaystyle{ O(n^2) }[/math], поэтому вычисление [math]\displaystyle{ x^{2^k} \bmod f_z(x) }[/math] делается за [math]\displaystyle{ O(n^2 \log p) }[/math],
  3. Аналогично предыдущему пункту, двоичное возведение в степень делается за [math]\displaystyle{ O(n^2 \log p) }[/math],
  4. Взятие [math]\displaystyle{ \gcd }[/math] от двух многочленов по алгоритму Евклида делается за [math]\displaystyle{ O(n^2) }[/math].

Таким образом, одна итерация алгоритма может быть произведена за [math]\displaystyle{ O(n^2 \log p) }[/math] арифметических операций с элементами [math]\displaystyle{ \mathbb F_p }[/math], а нахождение всех корней многочлена требует в среднем [math]\displaystyle{ O(n^2 \log n \log p) }[/math][8]. В частном случае извлечения квадратного корня величина [math]\displaystyle{ n }[/math] равна двум, поэтому время работы оценивается как [math]\displaystyle{ O(\log p) }[/math] на одну итерацию алгоритма[12].

Примечания

  1. ↑ 1,00 1,01 1,02 1,03 1,04 1,05 1,06 1,07 1,08 1,09 1,10 Berlekamp E. R. Factoring polynomials over large finite fields (англ.) // Mathematics of Computation. — 1970. — Vol. 24, iss. 111. — P. 730—732. — ISSN 0025-5718. — doi:10.1090/S0025-5718-1970-0276200-X.
  2. ↑ 2,0 2,1 2,2 2,3 2,4 Rabin M. Probabilistic Algorithms in Finite Fields (англ.) // SIAM Journal on Computing. — 1980. — 1 May (vol. 9, iss. 2). — P. 273—280. — ISSN 0097-5397. — doi:10.1137/0209024. Архивировано 23 июня 2019 года.
  3. ↑ 3,0 3,1 Berlekamp E. R. Factoring polynomials over finite fields (англ.) // The Bell System Technical Journal. — 1967. — October (vol. 46, iss. 8). — P. 1853—1859. — ISSN 0005-8580. — doi:10.1002/j.1538-7305.1967.tb03174.x. Архивировано 17 февраля 2019 года.
  4. ↑ 4,0 4,1 4,2 4,3 4,4 Knuth D. E. The art of computer programming (англ.). — Reading, Massachusetts: Addison-Wesley Publishing Company, 1968. — Vol. 2. — P. 381—390. — 624 p. — ISBN 0-201-03802-1. Архивная копия от 3 августа 2019 на Wayback Machine
  5. ↑ Sze T. W. On taking square roots without quadratic nonresidues over finite fields (англ.) // Mathematics of Computation. — 2011. — 3 January (vol. 80, iss. 275). — P. 1797—1811. — ISSN 0025-5718. — doi:10.1090/s0025-5718-2011-02419-1.
  6. ↑ Peralta R. A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.) (англ.) // IEEE Transactions on Information Theory. — 1986. — November (vol. 32, iss. 6). — P. 846—847. — ISSN 0018-9448. — doi:10.1109/TIT.1986.1057236. Архивировано 30 июня 2019 года.
  7. ↑ Padró C., Sáez G. Taking cube roots in Zm (англ.) // Applied Mathematics Letters. — 2002. — August (vol. 15, iss. 6). — P. 703—708. — ISSN 0893-9659. — doi:10.1016/s0893-9659(02)00031-9.
  8. ↑ 8,0 8,1 8,2 Ben-Or M. Probabilistic algorithms in finite fields (англ.) // 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981). — 1981. — October. — P. 394—398. — doi:10.1109/SFCS.1981.37. Архивировано 29 июля 2019 года.
  9. ↑ Camion P. A Deterministic Algorithm for Factorizing Polynomials of Fq [X] (англ.) // Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics. — Elsevier, 1983. — P. 149—157. — ISBN 9780444865120.
  10. ↑ Grenet B., van der Hoeven J., Lecerf G. Deterministic root finding over finite fields using Graeffe transforms (англ.) // Applicable Algebra in Engineering, Communication and Computing. — 2015. — Vol. 27, iss. 3. — P. 239. — ISSN 0938-1279. — doi:10.1007/s00200-015-0280-5.
  11. ↑ Golomb S. W., Hales A., Welch L. R. On the factorization of trinomials over GF(2) (англ.) // Shift Register Sequences. — World Scientific, 2017. — March. — P. 90—108. — ISBN 978-981-4632-00-3. — doi:10.1142/9789814632010_0005.
  12. ↑ 12,0 12,1 12,2 12,3 12,4 Menezes A. J., Blake I. F., Gao X. H., Mullin R. C., Vanstone S. A. Applications of Finite Fields (англ.). — Springer US, 1993. — P. 22—26. — 218 p. — (The Springer International Series in Engineering and Computer Science). — ISBN 9780792392828. Архивная копия от 30 июня 2019 на Wayback Machine
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Алгоритм_Берлекэмпа_—_Рабина&oldid=5852876