Алгоритм Берлекэмпа — Рабина
Алгоритм Берлекэмпа — Рабина (также метод Берлекэмпа) — вероятностный метод нахождения корней многочленов над полем с полиномиальной сложностью. Метод был описан американским математиком Элвином Берлекэмпом в 1970 году[1] в качестве побочного к алгоритму факторизации многочленов над конечными полями и позже (в 1979 году) был доработан Михаэлем Рабином для случая произвольных конечных полей[2]. Изначальная версия алгоритма, предложенная Берлекэмпом в 1967 году[3], не была полиномиальной[4]. Опубликованная в 1970 году на основе результатов Цассенхауза[англ.] версия алгоритма работала с большими значениями , в ней заглавный метод использовался в качестве вспомогательного[1]. На момент публикации метод был распространён в профессиональной среде, однако редко встречался в литературе[4].
История
Метод был предложен Элвином Берлекэмпом в его работе по факторизации многочленов над конечными полями[1]. В ней факторизация многочлена на неприводимые сомножители над полем сводится к нахождению корней некоторых других многочленов над полем . При этом в оригинальной работе отсутствовало доказательство корректности алгоритма[2]. Алгоритм был доработан и обобщён на случай произвольных конечных полей Михаэлем Рабином[2]. В 1986 году Рене Перальта описал похожий алгоритм[5], решающий задачу нахождения квадратного корня в поле [6], а в 2000 году метод Перальты был обобщён для решения кубических уравнений[7].
В алгоритме Берлекэмпа многочлен сперва представляется в виде произведения , где — произведение многочленов степени . Затем факторизация каждого такого многочлена степени сводится к поиску корней нового многочлена степени . В статье, вводящей алгоритм факторизации, было также предложено три метода для поиска корней многочлена в поле Галуа . Первые два сводят нахождение корней в поле к поиску корней в поле . Третий метод, являющийся предметом данной статьи, решает задачу поиска корней в поле , что вместе с двумя другими решает задачу факторизации[1].
Версия алгоритма факторизации, предложенная Берлекэмпом в его первой работе в 1967 г.[3], работала за , где — количество неприводимых сомножителей многочлена. Таким образом, алгоритм являлся неполиномиальным и был непрактичным в случае, когда простое число было достаточно большим. В 1969 г. эта проблема была решена Хансом Цассенхаузом[англ.], показавшим, как свести узкое место алгоритма к задаче поиска корней некоторого многочлена[4]. В 1970 г. статья Берлекэмпа была переиздана уже с учётом решений Цассенхауза[1].
В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида и доказал, что вероятность ошибки одной итерации алгоритма не превосходит [2], а в 1981 г. Михаэль Бен-Ор усилил эту оценку до , где — количество различных корней многочлена [8]. Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Алгоритм Кантора — Цассенхауза[англ.] являются вероятностными. В 1981 году Поль Камьон[фр.] показал[9], что такой алгоритм существует для любого наперёд заданного числа , однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым[10].
В первом издании второго тома «Искусства программирования» про получисленные алгоритмы Дональд Кнут пишет, что аналогичные процедуры факторизации были известны к 1960 г., однако редко встречались в открытом доступе[4]. Один из первых опубликованных примеров использования метода можно обнаружить в работе Голомба, Велша[англ.] и Хейлса[англ.] от 1959 года о факторизации трёхчленов над , где рассматривался частный случай [11].
Алгоритм
Постановка задачи
Пусть — нечётное простое число. Рассмотрим многочлен над полем остатков по модулю . Необходимо найти все числа такие что для всех возможных [2][12].
Рандомизация
Пусть . Нахождение всех корней такого многочлена равносильно его разбиению на линейные множители. Чтобы найти такое разбиение, достаточно научиться разбивать многочлен на любые два множителя, а затем запускаться в них рекурсивно. Для этого вводится в рассмотрение многочлен , где — случайное число из . Если такой многочлен можно представить в виде произведения , то в терминах исходного многочлена это значит, что , что даёт разбиение на множители исходного многочлена [1][12].
Классификация элементов
По критерию Эйлера для любого монома выполнено ровно одно из следующих свойств[1]:
- Одночлен равен , если ,
- Одночлен делит , если — квадратичный вычет по модулю ,
- Одночлен делит , если — квадратичный невычет по этому модулю.
Таким образом, если не делится на , что можно проверить отдельно, то равно произведению наибольших общих делителей и [12].
Метод Берлекэмпа
Написанное выше приводит к следующему алгоритму[1]:
- В явном виде вычисляются коэффициенты многочлена ,
- Вычисляются остатки от деления на последовательным возведением в квадрат и взятием остатка от ,
- Двоичным возведением в степень вычисляется остаток от деления на с использованием посчитанных на прошлом шаге многочленов,
- Если , то указанные выше дают нетривиальное разбиение на множители,
- В противном случае все корни являются вычетами или невычетами одновременно и стоит попробовать другое значения .
Если также делится на некоторый многочлен , не имеющий корней в , то при подсчёте с и будет получено разбиение бесквадратного многочлена на нетривиальные сомножители, поэтому алгоритм позволяет найти все корни любых многочленов над , а не только тех, которые разбиваются в произведение мономов[12].
Извлечение квадратного корня
Пусть нужно решить сравнение , решениями которого являются элементы и соответственно. Их нахождение эквивалентно факторизации многочлена над полем . В таком частном случае задача упрощается, так как для решения достаточно посчитать только . Для полученного многочлена будет верно ровно одно из утверждений:
- НОД равен , из чего следует, что и являются квадратичными невычетами одновременно,
- НОД равен , из чего следует, что оба числа являются квадратичными вычетами,
- НОД равен одночлену , из чего следует, что ровно одно число из двух является квадратичным вычетом.
В третьем случае полученный одночлен должен быть равен или , или . Это позволяет записать решение в виде [1].
Пример
Пусть нужно решить сравнение . Для этого нужно факторизовать . Рассмотрим возможные значения :
- Пусть . Тогда , откуда . Оба числа являются невычетами и нужно брать другое .
- Пусть . Тогда , откуда . Отсюда , значит и .
Проверка показывает, что действительно и .
Обоснование метода
Алгоритм находит разбиение на нетривиальные множители во всех случаях, за исключением тех, в которых все числа являются вычетами или невычетами одновременно. Согласно теории циклотомии[1], вероятность такого события для случая, когда сами одновременно являются вычетами или невычетами одновременно (то есть, когда не подходит для нашей процедуры), можно оценить как [8], где — количество различных чисел среди [1]. Таким образом, вероятность ошибки алгоритма не превосходит .
Применение к факторизации многочленов
Из теории конечных полей известно, что если степень неприводимого многочлена равна , то такой многочлен является делителем и не является делителем для .
Таким образом, последовательно рассматривая многочлены где и для , можно разбить многочлен на множители вида , где — это произведение всех неприводимых многочленов степени , которые делят многочлен . Зная степень , можно определить количество таких многочленов, равное . Пусть . Если рассмотреть многочлен , где , то порядок такого многочлена в поле должен делить число . Если не делится на , то многочлен делится на , но не на .
Исходя из этого Цассенхауз[англ.] предложил искать делители многочлена в виде , где — некоторый достаточно большой делитель , например, . В частном случае получается в точности метод Берлекэмпа как он описан выше[4].
Время работы
Поэтапно время работы одной итерации алгоритма можно оценить следующим образом, считая степень многочлена равной :
- Учитывая, что по формуле бинома Ньютона, переход от к делается за ,
- Произведение многочленов и взятие остатка от одного многочлена по модулю другого делается за , поэтому вычисление делается за ,
- Аналогично предыдущему пункту, двоичное возведение в степень делается за ,
- Взятие от двух многочленов по алгоритму Евклида делается за .
Таким образом, одна итерация алгоритма может быть произведена за арифметических операций с элементами , а нахождение всех корней многочлена требует в среднем [8]. В частном случае извлечения квадратного корня величина равна двум, поэтому время работы оценивается как на одну итерацию алгоритма[12].
Примечания
- ↑ 1 2 3 4 5 6 7 8 9 10 11 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.
- ↑ 1 2 3 4 5 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 года.
- ↑ 1 2 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 года.
- ↑ 1 2 3 4 5 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 года.
- ↑ 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.
- ↑ 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 года.
- ↑ 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.
- ↑ 1 2 3 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 года.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 1 2 3 4 5 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 года.