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

Метод Берлекэмпа(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).