Алгоритм Берлекампа – Рабина - Berlekamp–Rabin algorithm

В теория чисел, Алгоритм поиска корня Берлекампа, также называемый Алгоритм Берлекампа – Рабина, это вероятностный метод поиск корней из многочлены через поле ${ displaystyle mathbb {Z} _ {p}}$ . Метод был открыт Элвин Берлекамп в 1970 году^[1] как вспомогательное средство алгоритм для полиномиальной факторизации над конечными полями. Позднее алгоритм был изменен Рабин для произвольных конечных полей в 1979 г.^[2] Этот метод был также независимо открыт до Берлекампа другими исследователями.^[3]

История

Метод был предложен Элвин Берлекамп в его работе 1970 года^[1] о полиномиальной факторизации над конечными полями. Его оригинальной работе не хватало формального правильность доказательство^[2] и позже был уточнен и модифицирован для произвольных конечных полей Майкл Рабин.^[2] В 1986 году Рене Перальта предложил похожий алгоритм.^[4] для нахождения квадратных корней в ${ displaystyle mathbb {Z} _ {p}}$ .^[5] В 2000 г. метод Перальты был обобщен на кубические уравнения.^[6]

Постановка проблемы

Позволять ${ displaystyle p}$ нечетное простое число. Рассмотрим многочлен ${ textstyle f (x) = a_ {0} + a_ {1} x + cdots + a_ {n} x ^ {n}}$ над полем ${ displaystyle mathbb {Z} _ {p}}$ остатков по модулю ${ displaystyle p}$ . Алгоритм должен найти все ${ displaystyle lambda}$ в ${ displaystyle mathbb {Z} _ {p}}$ такой, что ${ textstyle f ( lambda) = 0}$ в ${ displaystyle mathbb {Z} _ {p}}$ .^[2]^[7]

Алгоритм

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

Позволять ${ textstyle f (x) = (x- lambda _ {1}) (x- lambda _ {2}) cdots (x- lambda _ {n})}$ . Нахождение всех корней этого многочлена эквивалентно нахождению его разложения на линейные множители. Чтобы найти такую факторизацию, достаточно разбить многочлен на любые два нетривиальных делителя и рекурсивно разложить их на множители. Для этого рассмотрим полином ${ textstyle f_ {z} (x) = f (xz) = (x- lambda _ {1} -z) (x- lambda _ {2} -z) cdots (x- lambda _ {n } -z)}$ где ${ displaystyle z}$ какой-нибудь элемент ${ displaystyle mathbb {Z} _ {p}}$ . Если можно представить этот многочлен как произведение ${ displaystyle f_ {z} (x) = p_ {0} (x) p_ {1} (x)}$ то в терминах исходного полинома это означает, что ${ Displaystyle f (x) = p_ {0} (x + z) p_ {1} (x + z)}$ , что обеспечивает необходимую факторизацию ${ displaystyle f (x)}$ .^[1]^[7]

Классификация ${ displaystyle mathbb {Z} _ {p}}$ элементы

Из-за Критерий Эйлера, для каждого одночлен ${ Displaystyle (х- лямбда)}$ выполняется ровно одно из следующих свойств:^[1]

Моном равен ${ displaystyle x}$ если ${ displaystyle lambda = 0}$ ,
Моном делит ${ textstyle g_ {0} (х) = (х ^ {(р-1) / 2} -1)}$ если ${ displaystyle lambda}$ является квадратичный вычет по модулю ${ displaystyle p}$ ,
Моном делит ${ textstyle g_ {1} (х) = (х ^ {(р-1) / 2} +1)}$ если ${ displaystyle lambda}$ квадратично не остаточно по модулю ${ displaystyle p}$ .

Таким образом, если ${ displaystyle f_ {z} (x)}$ не делится на ${ displaystyle x}$ , что можно проверить отдельно, то ${ displaystyle f_ {z} (x)}$ равен произведению наибольшие общие делители ${ displaystyle gcd (f_ {z} (x); g_ {0} (x))}$ и ${ Displaystyle НОД (е_ {г} (х); г_ {1} (х))}$ .^[7]

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

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

Явно вычислите коэффициенты ${ displaystyle f_ {z} (x) = f (x-z)}$ ,
Рассчитать остаток от ${ textstyle x, x ^ {2}, x ^ {2 ^ {2}}, x ^ {2 ^ {3}}, x ^ {2 ^ {4}}, ldots, x ^ {2 ^ { lfloor log _ {2} p rfloor}}}$ по модулю ${ displaystyle f_ {z} (x)}$ возводя в квадрат текущий полином и взяв остаток по модулю ${ displaystyle f_ {z} (x)}$ ,
С помощью возведение в степень возведением в квадрат а полиномы, вычисленные на предыдущих шагах, вычисляют остаток от ${ textstyle х ^ {(п-1) / 2}}$ по модулю ${ textstyle f_ {z} (x)}$ ,
Если ${ textstyle х ^ {(р-1) / 2} not Equiv pm 1 { pmod {f_ {z} (x)}}}$ тогда ${ displaystyle gcd}$ упомянутые выше обеспечивают нетривиальную факторизацию ${ displaystyle f_ {z} (x)}$ ,
В противном случае все корни ${ displaystyle f_ {z} (x)}$ являются либо остатками, либо не остатками одновременно, и нужно выбрать другой ${ displaystyle z}$ .

Если ${ displaystyle f (x)}$ делится на некоторую нелинейную примитивный многочлен ${ displaystyle g (x)}$ над ${ displaystyle mathbb {Z} _ {p}}$ тогда при расчете ${ displaystyle gcd}$ с участием ${ displaystyle g_ {0} (х)}$ и ${ displaystyle g_ {1} (х)}$ получится нетривиальная факторизация ${ displaystyle f_ {z} (x) / g_ {z} (x)}$ , таким образом, алгоритм позволяет находить все корни произвольных многочленов над ${ displaystyle mathbb {Z} _ {p}}$ .

Модульный квадратный корень

Рассмотрим уравнение ${ textstyle х ^ {2} эквив а { pmod {p}}}$ имеющий элементы ${ displaystyle beta}$ и ${ displaystyle - beta}$ как его корни. Решение этого уравнения эквивалентно факторизации полинома ${ textstyle f (x) = x ^ {2} -a = (x- beta) (x + beta)}$ над ${ displaystyle mathbb {Z} _ {p}}$ . В этом частном случае задачи достаточно вычислить только ${ displaystyle gcd (f_ {z} (x); g_ {0} (x))}$ . Для этого многочлена будет выполняться ровно одно из следующих свойств:

GCD невероятно похож на ${ displaystyle 1}$ которое значит что ${ displaystyle z + beta}$ и ${ displaystyle z- beta}$ оба квадратичных невычетов,
GCD невероятно похож на ${ displaystyle f_ {z} (x)}$ что означает, что оба числа являются квадратичными вычетами,
GCD невероятно похож на ${ Displaystyle (х-т)}$ что означает, что ровно одно из этих чисел является квадратичным вычетом.

В третьем случае НОД равен либо ${ Displaystyle (х-я- бета)}$ или ${ Displaystyle (х-г + бета)}$ . Это позволяет записать решение в виде ${ textstyle бета = (т-я) { pmod {p}}}$ .^[1]

пример

Предположим, нам нужно решить уравнение ${ textstyle х ^ {2} эквив 5 { pmod {11}}}$ . Для этого нам нужно разложить на множители ${ Displaystyle е (х) = х ^ {2} -5 = (х- бета) (х + бета)}$ . Рассмотрим некоторые возможные значения ${ displaystyle z}$ :

Позволять ${ displaystyle z = 3}$ . потом ${ displaystyle f_ {z} (x) = (x-3) ^ {2} -5 = x ^ {2} -6x + 4}$ , таким образом ${ displaystyle gcd (x ^ {2} -6x + 4; x ^ {5} -1) = 1}$ . Оба числа ${ displaystyle 3 pm beta}$ являются квадратичными невычетами, поэтому нам нужно взять другие ${ displaystyle z}$ .

Позволять ${ displaystyle z = 2}$ . потом ${ displaystyle f_ {z} (x) = (x-2) ^ {2} -5 = x ^ {2} -4x-1}$ , таким образом ${ textstyle gcd (x ^ {2} -4x-1; x ^ {5} -1) Equiv x-9 { pmod {11}}}$ . Из этого следует ${ textstyle х-9 = х-2- бета}$ , так ${ Displaystyle бета эквив 7 { pmod {11}}}$ и ${ textstyle - beta Equiv -7 Equ 4 { pmod {11}}}$ .

Проверка вручную показывает, что действительно ${ textstyle 7 ^ {2} эквив 49 экв 5 { pmod {11}}}$ и ${ textstyle 4 ^ {2} эквив 16 экв 5 { pmod {11}}}$ .

Доказательство правильности

Алгоритм находит факторизацию ${ displaystyle f_ {z} (x)}$ во всех случаях, кроме тех, когда все числа ${ displaystyle z + lambda _ {1}, z + lambda _ {2}, ldots, z + lambda _ {n}}$ являются квадратичными вычетами или невычетами одновременно. Согласно с теория циклотомии,^[8] вероятность такого события для случая, когда ${ displaystyle lambda _ {1}, ldots, lambda _ {n}}$ все остатки или не остатки одновременно (то есть, когда ${ displaystyle z = 0}$ потерпит неудачу) можно оценить как ${ displaystyle 2 ^ {- k}}$ где ${ displaystyle k}$ количество различных значений в ${ displaystyle lambda _ {1}, ldots, lambda _ {n}}$ .^[1] Таким образом, даже в худшем случае ${ displaystyle k = 1}$ и ${ Displaystyle е (х) = (х- лямбда) ^ {п}}$ , вероятность ошибки можно оценить как ${ displaystyle 1/2}$ а для случая модульного квадратного корня вероятность ошибки не превосходит ${ displaystyle 1/4}$ .

Сложность

Пусть многочлен имеет степень ${ displaystyle n}$ . Получим сложность алгоритма следующим образом:

Из-за биномиальная теорема ${ textstyle (x-z) ^ {k} = sum limits _ {i = 0} ^ {k} { binom {k} {i}} (- z) ^ {k-i} x ^ {i}}$ , мы можем перейти от ${ displaystyle f (x)}$ к ${ Displaystyle f (х-я)}$ в ${ Displaystyle О (п ^ {2})}$ время.
Умножение полиномов и взятие остатка от одного полинома по модулю другого можно выполнить в ${ textstyle O (п ^ {2})}$ , таким образом, расчет ${ textstyle x ^ {2 ^ {k}} { bmod {f}} _ {z} (x)}$ делается в ${ textstyle O (п ^ {2} log p)}$ .
Двоичное возведение в степень работает в ${ Displaystyle О (п ^ {2} журнал р)}$ .
Принимая ${ displaystyle gcd}$ двух полиномов через Евклидов алгоритм работает в ${ Displaystyle О (п ^ {2})}$ .

Таким образом, вся процедура может быть выполнена в ${ Displaystyle О (п ^ {2} журнал р)}$ . С использованием быстрое преобразование Фурье и алгоритм Half-GCD,^[9] сложность алгоритма может быть улучшена до ${ Displaystyle О (п войти п войти pn)}$ . Для модульного случая квадратного корня степень равна ${ displaystyle n = 2}$ , поэтому вся сложность алгоритма в таком случае ограничена ${ Displaystyle О ( журнал р)}$ за итерацию.^[7]

использованная литература

^ ^а ^б ^c ^d ^е ^ж ^г Берлекамп, Э. Р. (1970). «Факторизация многочленов над большими конечными полями». Математика вычислений. 24 (111): 713–735. Дои:10.1090 / S0025-5718-1970-0276200-X. ISSN 0025-5718.
^ ^а ^б ^c ^d М. Рабин (1980). «Вероятностные алгоритмы в конечных полях». SIAM Журнал по вычислениям. 9 (2): 273–280. Дои:10.1137/0209024. ISSN 0097-5397.
^ Дональд Э. Кнут (1998). Искусство программирования. Vol. 2 т. 2. ISBN 978-0201896848. OCLC 900627019.
^ Цз-Во Сзе (2011). «О извлечении квадратных корней без квадратичных невычетов над конечными полями». Математика вычислений. 80 (275): 1797–1811. arXiv:0812.2591. Дои:10.1090 / s0025-5718-2011-02419-1. ISSN 0025-5718.
^ Р. Перальта (ноябрь 1986 г.). «Простой и быстрый вероятностный алгоритм для вычисления квадратных корней по модулю простого числа (Corresp.)». IEEE Transactions по теории информации. 32 (6): 846–847. Дои:10.1109 / TIT.1986.1057236. ISSN 0018-9448.
^ С. Падро, Г. Саез (август 2002 г.). «Корни куба в Zm». Письма по прикладной математике. 15 (6): 703–708. Дои:10.1016 / s0893-9659 (02) 00031-9. ISSN 0893-9659.
^ ^а ^б ^c ^d Альфред Дж. Менезес, Ян Ф. Блейк, Сю Хонг Гао, Рональд К. Маллин, Скотт А. Ванстон (1993). Приложения конечных полей. Серия Springer International в области инженерии и информатики. Springer США. ISBN 9780792392828.CS1 maint: несколько имен: список авторов (ссылка на сайт)
^ Маршалл Холл (1998). Комбинаторная теория. Джон Вили и сыновья. ISBN 9780471315186.
^ Ахо, Альфред В. (1974). Разработка и анализ компьютерных алгоритмов. Аддисон-Уэсли Паб. Co. ISBN 0201000296.

[:0-1] а ^б ^c ^d ^е ^ж ^г Берлекамп, Э. Р. (1970). «Факторизация многочленов над большими конечными полями». Математика вычислений. 24 (111): 713–735. Дои:10.1090 / S0025-5718-1970-0276200-X. ISSN 0025-5718.

[:1-2] а ^б ^c ^d М. Рабин (1980). «Вероятностные алгоритмы в конечных полях». SIAM Журнал по вычислениям. 9 (2): 273–280. Дои:10.1137/0209024. ISSN 0097-5397.

[3] Дональд Э. Кнут (1998). Искусство программирования. Vol. 2 т. 2. ISBN 978-0201896848. OCLC 900627019.

[4] Цз-Во Сзе (2011). «О извлечении квадратных корней без квадратичных невычетов над конечными полями». Математика вычислений. 80 (275): 1797–1811. arXiv:0812.2591. Дои:10.1090 / s0025-5718-2011-02419-1. ISSN 0025-5718.

[5] Р. Перальта (ноябрь 1986 г.). «Простой и быстрый вероятностный алгоритм для вычисления квадратных корней по модулю простого числа (Corresp.)». IEEE Transactions по теории информации. 32 (6): 846–847. Дои:10.1109 / TIT.1986.1057236. ISSN 0018-9448.

[6] С. Падро, Г. Саез (август 2002 г.). «Корни куба в Zm». Письма по прикладной математике. 15 (6): 703–708. Дои:10.1016 / s0893-9659 (02) 00031-9. ISSN 0893-9659.

[:2-7] а ^б ^c ^d Альфред Дж. Менезес, Ян Ф. Блейк, Сю Хонг Гао, Рональд К. Маллин, Скотт А. Ванстон (1993). Приложения конечных полей. Серия Springer International в области инженерии и информатики. Springer США. ISBN 9780792392828.CS1 maint: несколько имен: список авторов (ссылка на сайт)

[8] Маршалл Холл (1998). Комбинаторная теория. Джон Вили и сыновья. ISBN 9780471315186.

[9] Ахо, Альфред В. (1974). Разработка и анализ компьютерных алгоритмов. Аддисон-Уэсли Паб. Co. ISBN 0201000296.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Теоретико-числовой алгоритмы
Тесты на первичность	AKS APR Бэйли – PSW Эллиптическая кривая Pocklington Ферма Лукас Лукас – Лемер Лукас – Лемер – Ризель Теорема прота Пепина Квадратичный Фробениус Соловей-Штрассен Миллер – Рабин
Прайм-генерирующий	Сито Аткина Сито Эратосфена Сито Сундарама Факторизация колес
Целочисленная факторизация	Непрерывная дробь (CFRAC) Диксона Эллиптическая кривая Ленстры (ECM) Эйлера Ро Полларда п − 1 п + 1 Квадратичное сито (QS) Сито общего числового поля (GNFS) Сито специального номерного поля (SNFS) Рациональное сито Ферма Квадратные формы Шанкса Судебное отделение Шора
Умножение	Древнеегипетский Длинная Карацуба Тоом – Кук Шёнхаге-Штрассен Фюрера
Евклидово деление	Двоичный Разбивка Фурье Гольдшмидт Ньютон-Рафсон Длинная короткий SRT
Дискретный логарифм	Бэби-степ гигантский шаг Поллард ро Кенгуру Полларда Pohlig – Hellman Расчет индекса Функциональное поле сито
Наибольший общий делитель	Двоичный Евклидово Расширенное евклидово Лемера
Модульный квадратный корень	Чиполла Поклингтона Тонелли-Шанкс Берлекамп
Другие алгоритмы	Чакравала Корнаккия Возведение в степень возведением в квадрат Целочисленный квадратный корень Целочисленное отношение (LLL ) Модульное возведение в степень Редукция Монтгомери Schoof
Курсив указывают, что алгоритм предназначен для номеров специальных форм