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

Метод Берлекэмпа(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
 \texttt        (x-3)\texttt2\texttt - 5 = 0(mod 11);\\\texttt         x\texttt2\texttt - 6x + 4 = 0(mod 11);\\\texttt         G\textttz\texttt(x) = НОД( x\texttt2\texttt - 6x + 4 ; x\texttt5\texttt - 1) = 1;
 Ничего определенного сказать нельзя. Выберем другое z, например z=2
 \texttt        (x-2)\texttt2\texttt - 5 = 0(mod 11);\\\texttt         x\texttt2\texttt - 4x - 1 = 0(mod 11);\\\texttt         G\textttz\texttt(x) = НОД( x\texttt2\texttt - 4x - 1 ; x\texttt5\texttt - 1) = 8x + 5 = x + 2 = x - 9;\\\texttt         x - 9 = x - 2 + β =\textgreater β = 7 и β = -7 = 4.
 Проверяем
 \texttt         7\texttt2\texttt= 49 = 5(mod 11)\\\texttt         4\texttt2\texttt= 16 = 5(mod 11).