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


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

История

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

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

В алгоритме Берлекэмпа многочлен f ( x ) = a 0 + a 1 x + ⋯ + a n x n {displaystyle f(x)=a_{0}+a_{1}x+dots +a_{n}x^{n}} сперва представляется в виде произведения f ( x ) = h 1 ( x ) h 2 ( x ) … h n ( x ) {displaystyle f(x)=h_{1}(x)h_{2}(x)dots h_{n}(x)} , где h i {displaystyle h_{i}} — произведение r i {displaystyle r_{i}} многочленов степени i {displaystyle i} . Затем факторизация каждого такого многочлена h i ( x ) {displaystyle h_{i}(x)} степени i r i {displaystyle ir_{i}} сводится к поиску корней нового многочлена H ( x ) {displaystyle H(x)} степени r i {displaystyle r_{i}} . В статье, вводящей алгоритм факторизации, было также предложено три метода для поиска корней многочлена в поле Галуа F p k {displaystyle mathbb {F} _{p^{k}}} . Первые два сводят нахождение корней в поле F p k {displaystyle mathbb {F} _{p^{k}}} к поиску корней в поле F p {displaystyle mathbb {F} _{p}} . Третий метод, являющийся предметом данной статьи, решает задачу поиска корней в поле F p {displaystyle mathbb {F} _{p}} , что вместе с двумя другими решает задачу факторизации.

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

В 1980 г. Михаэль Рабин провёл строгий анализ алгоритма, обобщил его для работы с конечным полями вида F p k {displaystyle mathbb {F} _{p^{k}}} и доказал, что вероятность ошибки одной итерации алгоритма не превосходит 1 / 2 {displaystyle 1/2} , а в 1981 г. Михаэль Бен-Ор усилил эту оценку до 1 − 1 / 2 k − 1 + O ( 1 / p ) { extstyle 1-1/2^{k-1}+Oleft(1/{sqrt {p}} ight)} , где k {displaystyle k} — количество различных корней многочлена f ( x ) {displaystyle f(x)} . Вопрос существования полиномиального детерминированного алгоритма для нахождения корней многочлена над конечным полем остаётся открытым — основные алгоритмы факторизации многочленов, алгоритм Берлекэмпа и Алгоритм Кантора — Цассенхауза являются вероятностными. В 1981 году Поль Камьон показал, что такой алгоритм существует для любого наперёд заданного числа p {displaystyle p} , однако этот результат исключительно теоретический и вопрос о возможности построения описанных им множеств на практике остаётся открытым.

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

Алгоритм

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

Пусть p {displaystyle p} — нечётное простое число. Рассмотрим многочлен f ( x ) = a 0 + a 1 x + ⋯ + a n x n { extstyle f(x)=a_{0}+a_{1}x+dots +a_{n}x^{n}} над полем Z p {displaystyle mathbb {Z} _{p}} остатков по модулю p {displaystyle p} . Необходимо найти все числа λ 1 , … , λ k {displaystyle lambda _{1},dots ,lambda _{k}} такие что f ( λ i ) ≡ 0 ( mod p ) { extstyle f(lambda _{i})equiv 0{pmod {p}}} для всех возможных i {displaystyle i} .

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

Пусть f ( x ) = ( x − λ 1 ) ( x − λ 2 ) … ( x − λ n ) { extstyle f(x)=(x-lambda _{1})(x-lambda _{2})dots (x-lambda _{n})} . Нахождение всех корней такого многочлена равносильно его разбиению на линейные множители. Чтобы найти такое разбиение, достаточно научиться разбивать многочлен на любые два множителя, а затем запускаться в них рекурсивно. Для этого вводится в рассмотрение многочлен f z ( x ) = f ( x − z ) = ( x − λ 1 − z ) ( x − λ 2 − z ) … ( x − λ n − z ) { extstyle f_{z}(x)=f(x-z)=(x-lambda _{1}-z)(x-lambda _{2}-z)dots (x-lambda _{n}-z)} , где z {displaystyle z} — случайное число из Z p {displaystyle mathbb {Z} _{p}} . Если такой многочлен можно представить в виде произведения f z ( x ) = p 0 ( x ) p 1 ( x ) {displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)} , то в терминах исходного многочлена это значит, что f ( x ) = p 0 ( x + z ) p 1 ( x + z ) {displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)} , что даёт разбиение на множители исходного многочлена f ( x ) {displaystyle f(x)} .

Классификация элементов F p {displaystyle mathbb {F} _{p}}

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

  • Одночлен равен x {displaystyle x} , если λ = 0 {displaystyle lambda =0} ,
  • Одночлен делит g 0 ( x ) = ( x ( p − 1 ) / 2 − 1 ) { extstyle g_{0}(x)=(x^{(p-1)/2}-1)} , если λ {displaystyle lambda } — квадратичный вычет по модулю p {displaystyle p} ,
  • Одночлен делит g 1 ( x ) = ( x ( p − 1 ) / 2 + 1 ) { extstyle g_{1}(x)=(x^{(p-1)/2}+1)} , если λ {displaystyle lambda } — квадратичный невычет по этому модулю.
  • Таким образом, если f z ( x ) {displaystyle f_{z}(x)} не делится на x {displaystyle x} , что можно проверить отдельно, то f z ( x ) {displaystyle f_{z}(x)} равно произведению наибольших общих делителей gcd ( f z ( x ) ; g 0 ( x ) ) {displaystyle gcd(f_{z}(x);g_{0}(x))} и gcd ( f z ( x ) ; g 1 ( x ) ) {displaystyle gcd(f_{z}(x);g_{1}(x))} .

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

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

  • В явном виде вычисляются коэффициенты многочлена f z ( x ) = f ( x − z ) {displaystyle f_{z}(x)=f(x-z)} ,
  • Вычисляются остатки от деления x , x 2 , x 2 2 , x 2 3 , x 2 4 , … , x 2 ⌊ log 2 ⁡ p ⌋ { extstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},dots ,x^{2^{lfloor log _{2}p floor }}} на f z ( x ) {displaystyle f_{z}(x)} последовательным возведением в квадрат и взятием остатка от f z ( x ) {displaystyle f_{z}(x)} ,
  • Двоичным возведением в степень вычисляется остаток от деления x ( p − 1 ) / 2 { extstyle x^{(p-1)/2}} на f z ( x ) { extstyle f_{z}(x)} с использованием посчитанных на прошлом шаге многочленов,
  • Если x ( p − 1 ) / 2 ≢ ± 1 ( mod f z ( x ) ) { extstyle x^{(p-1)/2} ot equiv pm 1{pmod {f_{z}(x)}}} , то указанные выше gcd {displaystyle gcd } дают нетривиальное разбиение f z ( x ) {displaystyle f_{z}(x)} на множители,
  • В противном случае все корни f z ( x ) {displaystyle f_{z}(x)} являются вычетами или невычетами одновременно и стоит попробовать другое значения z {displaystyle z} .
  • Если f ( x ) {displaystyle f(x)} также делится на некоторый многочлен g ( x ) {displaystyle g(x)} , не имеющий корней в Z p {displaystyle mathbb {Z} _{p}} , то при подсчёте gcd {displaystyle gcd } с g 0 ( x ) {displaystyle g_{0}(x)} и g 1 ( x ) {displaystyle g_{1}(x)} будет получено разбиение бесквадратного многочлена f z ( x ) / g z ( x ) {displaystyle f_{z}(x)/g_{z}(x)} на нетривиальные сомножители, поэтому алгоритм позволяет найти все корни любых многочленов над Z p {displaystyle mathbb {Z} _{p}} , а не только тех, которые разбиваются в произведение мономов.

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

    Пусть нужно решить сравнение x 2 ≡ a ( mod p ) { extstyle x^{2}equiv a{pmod {p}}} , решениями которого являются элементы β {displaystyle eta } и − β {displaystyle -eta } соответственно. Их нахождение эквивалентно факторизации многочлена f ( x ) = x 2 − a = ( x − β ) ( x + β ) { extstyle f(x)=x^{2}-a=(x-eta )(x+eta )} над полем Z p {displaystyle mathbb {Z} _{p}} . В таком частном случае задача упрощается, так как для решения достаточно посчитать только gcd ( f z ( x ) ; g 0 ( x ) ) {displaystyle gcd(f_{z}(x);g_{0}(x))} . Для полученного многочлена будет верно ровно одно из утверждений:

  • НОД равен 1 {displaystyle 1} , из чего следует, что z + β {displaystyle z+eta } и z − β {displaystyle z-eta } являются квадратичными невычетами одновременно,
  • НОД равен f z ( x ) {displaystyle f_{z}(x)} , из чего следует, что оба числа являются квадратичными вычетами,
  • НОД равен одночлену ( x − t ) {displaystyle (x-t)} , из чего следует, что ровно одно число из двух является квадратичным вычетом.
  • В третьем случае полученный одночлен должен быть равен или ( x − z − β ) {displaystyle (x-z-eta )} , или ( x − z + β ) {displaystyle (x-z+eta )} . Это позволяет записать решение в виде β = ( t − z ) ( mod p ) { extstyle eta =(t-z){pmod {p}}} .

    Пример

    Пусть нужно решить сравнение x 2 ≡ 5 ( mod 11 ) { extstyle x^{2}equiv 5{pmod {11}}} . Для этого нужно факторизовать f ( x ) = x 2 − 5 = ( x − β ) ( x + β ) {displaystyle f(x)=x^{2}-5=(x-eta )(x+eta )} . Рассмотрим возможные значения z {displaystyle z} :

  • Пусть z = 3 {displaystyle z=3} . Тогда f z ( x ) = ( x − 3 ) 2 − 5 = x 2 − 6 x + 4 {displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4} , откуда gcd ( x 2 − 6 x + 4 ; x 5 − 1 ) = 1 {displaystyle gcd(x^{2}-6x+4;x^{5}-1)=1} . Оба числа 3 ± β {displaystyle 3pm eta } являются невычетами и нужно брать другое z {displaystyle z} .
  • Пусть z = 2 {displaystyle z=2} . Тогда f z ( x ) = ( x − 2 ) 2 − 5 = x 2 − 4 x − 1 {displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1} , откуда gcd ( x 2 − 4 x − 1 ; x 5 − 1 ) ≡ x − 9 ( mod 11 ) { extstyle gcd(x^{2}-4x-1;x^{5}-1)equiv x-9{pmod {11}}} . Отсюда x − 9 = x − 2 − β { extstyle x-9=x-2-eta } , значит β ≡ 7 ( mod 11 ) {displaystyle eta equiv 7{pmod {11}}} и − β ≡ − 7 ≡ 4 ( mod 11 ) { extstyle -eta equiv -7equiv 4{pmod {11}}} .
  • Проверка показывает, что действительно 7 2 ≡ 49 ≡ 5 ( mod 11 ) { extstyle 7^{2}equiv 49equiv 5{pmod {11}}} и 4 2 ≡ 16 ≡ 5 ( mod 11 ) { extstyle 4^{2}equiv 16equiv 5{pmod {11}}} .

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

    Алгоритм находит разбиение f z ( x ) {displaystyle f_{z}(x)} на нетривиальные множители во всех случаях, за исключением тех, в которых все числа z + λ 1 , z + λ 2 , … , z + λ n {displaystyle z+lambda _{1},z+lambda _{2},dots ,z+lambda _{n}} являются вычетами или невычетами одновременно. Согласно теории циклотомии, вероятность такого события для случая, когда λ 1 , … , λ n {displaystyle lambda _{1},dots ,lambda _{n}} сами одновременно являются вычетами или невычетами одновременно (то есть, когда z = 0 {displaystyle z=0} не подходит для нашей процедуры), можно оценить как 1 / 2 k − 1 {displaystyle 1/2^{k-1}} , где k {displaystyle k} — количество различных чисел среди λ 1 , … , λ n {displaystyle lambda _{1},dots ,lambda _{n}} . Таким образом, вероятность ошибки алгоритма не превосходит 1 / 2 {displaystyle 1/2} .

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

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

    Таким образом, последовательно рассматривая многочлены h i ( x ) = gcd ( f i ( x ) , x p i − 1 ) {displaystyle h_{i}(x)=gcd(f_{i}(x),x^{p^{i}}-1)} где f 1 ( x ) = f ( x ) {displaystyle f_{1}(x)=f(x)} и f i ( x ) = f i − 1 ( x ) / h i − 1 ( x ) {displaystyle f_{i}(x)=f_{i-1}(x)/h_{i-1}(x)} для i > 1 {displaystyle i>1} , можно разбить многочлен f ( x ) {displaystyle f(x)} на множители вида f ( x ) = h 1 ( x ) … h n ( x ) {displaystyle f(x)=h_{1}(x)dots h_{n}(x)} , где h i ( x ) {displaystyle h_{i}(x)} — это произведение всех неприводимых многочленов степени i {displaystyle i} , которые делят многочлен f ( x ) {displaystyle f(x)} . Зная степень h i ( x ) {displaystyle h_{i}(x)} , можно определить количество таких многочленов, равное r i = deg ⁡ h i ( x ) / i {displaystyle r_{i}=deg h_{i}(x)/i} . Пусть h i ( x ) = p 1 ( x ) … p r i ( x ) {displaystyle h_{i}(x)=p_{1}(x)dots p_{r_{i}}(x)} . Если рассмотреть многочлен p j ( x − z ) {displaystyle p_{j}(x-z)} , где z ∈ F p { extstyle zin mathbb {F} _{p}} , то порядок такого многочлена d j {displaystyle d_{j}} в поле F p i { extstyle mathbb {F} _{p^{i}}} должен делить число p i − 1 {displaystyle p^{i}-1} . Если d j {displaystyle d_{j}} не делится на d k {displaystyle d_{k}} , то многочлен x d j − x { extstyle x^{d_{j}}-x} делится на p j ( x − z ) { extstyle p_{j}(x-z)} , но не на p k ( x − z ) { extstyle p_{k}(x-z)} .

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

    Время работы

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

  • Учитывая, что ( x − z ) k = ∑ i = 0 k ( k i ) ( − z ) k − i x i { extstyle (x-z)^{k}=sum limits _{i=0}^{k}{inom {k}{i}}(-z)^{k-i}x^{i}} по формуле бинома Ньютона, переход от f ( x ) {displaystyle f(x)} к f ( x − z ) {displaystyle f(x-z)} делается за O ( n 2 ) {displaystyle O(n^{2})} ,
  • Произведение многочленов и взятие остатка от одного многочлена по модулю другого делается за O ( n 2 ) { extstyle O(n^{2})} , поэтому вычисление x 2 k mod f z ( x ) { extstyle x^{2^{k}}{mod {f}}_{z}(x)} делается за O ( n 2 log ⁡ p ) { extstyle O(n^{2}log p)} ,
  • Аналогично предыдущему пункту, двоичное возведение в степень делается за O ( n 2 log ⁡ p ) {displaystyle O(n^{2}log p)} ,
  • Взятие gcd {displaystyle gcd } от двух многочленов по алгоритму Евклида делается за O ( n 2 ) {displaystyle O(n^{2})} .
  • Таким образом, одна итерация алгоритма может быть произведена за O ( n 2 log ⁡ p ) {displaystyle O(n^{2}log p)} арифметических операций с элементами F p {displaystyle mathbb {F} _{p}} , а нахождение всех корней многочлена требует в среднем O ( n 2 log ⁡ n log ⁡ p ) {displaystyle O(n^{2}log nlog p)} . В частном случае извлечения квадратного корня величина n {displaystyle n} равна двум, поэтому время работы оценивается как O ( log ⁡ p ) {displaystyle O(log p)} на одну итерацию алгоритма.






    Яндекс.Метрика