WikiSort.ru - Не сортированное

Эта страница требует существенной переработки. Возможно, её необходимо викифицировать, дополнить или переписать. Пояснение причин и обсуждение — на странице Википедия:К улучшению/5 ноября 2018. Номинатору: добавить секцию обсуждения.

Метод Берлекэмпа(Berlekamp) - вероятностный метод решения сравнений второй степени с полиномиальной сложностью. При этом вероятность решения ½.

Описание метода

Задача: решить сравнение вида x² - a = 0(mod p) при простом p, a - квадратичный вычет. Обозначим решения как β и -β. F(x)=x² - a = (x-β)(x+β).

Рассмотрим произвольное число z, принадлежащее полю вычетов по модулю p. Обозначим F_z(x)=F(x-z)=(x-z)² - a = (x-z-β)(x-z+β) Рассмотрим G_z(x) = НОД(F_z(x);x^(p-1)/2 - 1), при этом учитывая, что x^(p-1)/2 - 1 можно представить в виде произведения мономов (x-t), где t - вычет по модулю p. Далее, если НОД равен 1, значит (z-β) и (z+β) не вычеты.

Если НОД равен F_z(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).

Для улучшения этой статьи желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.