Метод Берлекэмпа
Метод Берлекэмпа(Berlekamp) - вероятностный метод решения сравнений второй степени с полиномиальной сложностью. При этом вероятность решения ½.
Описание метода
Задача: решить сравнение вида x² - a = 0(mod p) при простом p, a - квадратичный вычет.
Обозначим решения как β и -β.
F(x)=x² - a = (x-β)(x+β).
Рассмотрим произвольное число z, принадлежащее полю вычетов по модулю p. Обозначим Fz(x)=F(x-z)=(x-z)2 - a = (x-z-β)(x-z+β)
Рассмотрим Gz(x) = НОД(Fz(x);x(p-1)/2 - 1), при этом учитывая, что x(p-1)/2 - 1 можно представить в виде произведения мономов (x-t), где t - вычет по модулю p.
Далее, если НОД равен 1, значит (z-β) и (z+β) не вычеты.
Если НОД равен Fz(x) оба вычеты, но выразить x не удастся.
Если НОД равен некоторому (x - t), который в свою очередь равен (x-z-β) или (x-z+β), мы можем выразить через него решение x.
В итоге, так как x произвольное получаем вероятностный метод решения сравнения 2-й степени с вероятностью решения 1/2 и полиномиальной сложностью решения (нахождение НОД имеет полиномиальную сложность).
Метод хорош тем, что позволяет не решать задачу дискретного логарифмирования.
Пример
x² - 5 = 0(mod 11) Выберем случайное z, например z=3
(x-3)2 - 5 = 0(mod 11);
x2 - 6x + 4 = 0(mod 11);
Gz(x) = НОД( x2 - 6x + 4 ; x5 - 1) = 1;
Ничего определенного сказать нельзя. Выберем другое z, например z=2
(x-2)2 - 5 = 0(mod 11);
x2 - 4x - 1 = 0(mod 11);
Gz(x) = НОД( x2 - 4x - 1 ; x5 - 1) = 8x + 5 = x + 2 = x - 9;
x - 9 = x - 2 + β => β = 7 и β = -7 = 4.
Проверяем
72= 49 = 5(mod 11)
42= 16 = 5(mod 11).
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Напишите отзыв о статье "Метод Берлекэмпа"
Отрывок, характеризующий Метод Берлекэмпа
– Ну, а мальчик что?– Весенний то? Он там, в сенцах, завалился. Со страху спится. Уж рад то был.
Долго после этого Петя молчал, прислушиваясь к звукам. В темноте послышались шаги и показалась черная фигура.
– Что точишь? – спросил человек, подходя к фуре.
– А вот барину наточить саблю.
– Хорошее дело, – сказал человек, который показался Пете гусаром. – У вас, что ли, чашка осталась?
– А вон у колеса.
Гусар взял чашку.
– Небось скоро свет, – проговорил он, зевая, и прошел куда то.
Петя должен бы был знать, что он в лесу, в партии Денисова, в версте от дороги, что он сидит на фуре, отбитой у французов, около которой привязаны лошади, что под ним сидит казак Лихачев и натачивает ему саблю, что большое черное пятно направо – караулка, и красное яркое пятно внизу налево – догоравший костер, что человек, приходивший за чашкой, – гусар, который хотел пить; но он ничего не знал и не хотел знать этого. Он был в волшебном царстве, в котором ничего не было похожего на действительность. Большое черное пятно, может быть, точно была караулка, а может быть, была пещера, которая вела в самую глубь земли. Красное пятно, может быть, был огонь, а может быть – глаз огромного чудовища. Может быть, он точно сидит теперь на фуре, а очень может быть, что он сидит не на фуре, а на страшно высокой башне, с которой ежели упасть, то лететь бы до земли целый день, целый месяц – все лететь и никогда не долетишь. Может быть, что под фурой сидит просто казак Лихачев, а очень может быть, что это – самый добрый, храбрый, самый чудесный, самый превосходный человек на свете, которого никто не знает. Может быть, это точно проходил гусар за водой и пошел в лощину, а может быть, он только что исчез из виду и совсем исчез, и его не было.
