Русская Википедия:Алгоритм Берлекэмпа — Рабина

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Elwyn R Berlekamp 2005.jpg

Элвин Берлекэмп

Алгоритм Берлекэмпа — Рабина (также метод Берлекэмпа) — вероятностный метод нахождения корней многочленов над полем <math>\mathbb F_p</math>с полиномиальной сложностью. Метод был описан американским математиком Элвином Берлекэмпом в 1970 году в качестве побочного к алгоритму факторизации многочленов над конечными полями и позже (в 1979 году) был доработан Михаэлем Рабином для случая произвольных конечных полей. Изначальная версия алгоритма, предложенная Берлекэмпом в 1967 году, не была полиномиальной. Опубликованная в 1970 году на основе результатов Шаблон:Не переведено 5 версия алгоритма работала с большими значениями <math>p</math>, в ней заглавный метод использовался в качестве вспомогательного. На момент публикации метод был распространён в профессиональной среде, однако редко встречался в литературе.

История

Файл:M O Rabin.jpg

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

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

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

Версия алгоритма факторизации, предложенная Берлекэмпом в его первой работе в 1967 г., работала за <math>O(n^3+prn)</math>, где <math>r</math> — количество неприводимых сомножителей многочлена. Таким образом, алгоритм являлся неполиномиальным и был непрактичным в случае, когда простое число <math>p</math> было достаточно большим. В 1969 г. эта проблема была решена Шаблон:Не переведено 5, показавшим, как свести узкое место алгоритма к задаче поиска корней некоторого многочлена. В 1970 г. статья Берлекэмпа была переиздана уже с учётом решений Цассенхауза.

В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида <math>\mathbb F_{p^k}</math> и доказал, что вероятность ошибки одной итерации алгоритма не превосходит <math>1/2</math>, а в 1981 г. Михаэль Бен-Ор усилил эту оценку до <math display="inline">1-1/2^{k-1}+O\left(1/\sqrt{p}\right)</math>, где <math>k</math> — количество различных корней многочлена <math>f(x)</math>. Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Шаблон:Не переведено 5 являются вероятностными. В 1981 году Шаблон:Не переведено 5 показал, что такой алгоритм существует для любого наперёд заданного числа <math>p</math>, однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым.

В первом издании второго тома «Искусства программирования» про получисленные алгоритмы Дональд Кнут пишет, что аналогичные процедуры факторизации были известны к 1960 г., однако редко встречались в открытом доступе. Один из первых опубликованных примеров использования метода можно обнаружить в работе Голомба, Шаблон:Не переведено 5 и Шаблон:Не переведено 5 от 1959 года о факторизации трёхчленов над <math>\mathbb F_2</math>, где рассматривался частный случай <math>p=2,z=1</math>.

Алгоритм

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

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

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

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

Классификация элементов <math>\mathbb F_p</math>

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

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

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

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

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

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

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

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

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

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

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

Пример

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

1. Пусть <math>z=3</math>. Тогда <math>f_z(x) = (x-3)^2 - 5 = x^2 - 6x + 4</math>, откуда <math>\gcd(x^2 - 6x + 4 ; x^5 - 1) = 1</math>. Оба числа <math>3 \pm \beta</math> являются невычетами и нужно брать другое <math>z</math>.

1. Пусть <math>z=2</math>. Тогда <math>f_z(x) = (x-2)^2 - 5 = x^2 - 4x - 1</math>, откуда <math display = inline>\gcd( x^2 - 4x - 1 ; x^5 - 1)\equiv x - 9 \pmod{11}</math>. Отсюда <math display="inline">x - 9 = x - 2 - \beta</math>, значит <math>\beta \equiv 7 \pmod{11}</math> и <math display="inline">-\beta \equiv -7 \equiv 4 \pmod{11}</math>.

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

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

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

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

Шаблон:Основная статья Из теории конечных полей известно, что если степень неприводимого многочлена <math>q(x)</math> равна <math>d</math>, то такой многочлен является делителем <math>x^{p^d}-x</math> и не является делителем <math>x^{p^t}-x</math> для <math>t < d</math>.

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

Исходя из этого Шаблон:Не переведено 5 предложил искать делители многочлена <math>h_i(x-z)</math> в виде <math display="inline">\gcd(h_i(x-z), x^f-1)</math>, где <math>f</math> — некоторый достаточно большой делитель <math>p^i-1</math>, например, <math display="inline">f=\frac{p^i-1}{2}</math>. В частном случае <math>i=1</math> получается в точности метод Берлекэмпа как он описан выше.

Время работы

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

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

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