 |
|
Символы Лежандра и Якоби, извлечение квадратного корня.
В таблице 4 приведены значения символов Лежандра и Якоби, а также выводы, из них следующие.
Таблица 4
| Значение | L(a, p) | J(a, n) |
| Корень можно извлечь | Корень может быть можно извлечь | |
| a кратно p | a кратно n | |
| -1 (оно же p - 1 или n – 1) | Корень извлечь нельзя | Корень извлечь нельзя |
Как видно из таблицы символ Якоби однозначно дает только отрицательный ответ.
В общем случае символ Лежандра легко вычисляется по формуле: 
Но в реальных приложениях данный способ не используется ввиду своей высокой вычислительной сложности. На практике символы Лежандра и Якоби вычисляют по одинаковой рекуррентной зависимости приведенной ниже:
где: 
,
e – максимальная степень двойки на которую можно сократить a,
a1 – нечетный результат сокращения.
Условия выхода из рекурсии:
Следует отметить, что присутствующие в выражениях операции деления на 2, 4 и 8 легко реализуются программно путем правого битового сдвига на 1, 2 и 3 соответственно.
Извлечение квадратного корня по модулю простого числа 
легко выполняестя по следующей формуле:
В случае же 
, вычисление квадратного корня возможно только при помощи алгоритма Шенкса, чем на практике не пользуются ввиду его высокой вычислительной сложности.
Задача 2.2. Определить путем вычисления символа Якоби возможность извлечения квадратного корня из числа a по модулю простого числа p. Проверить правильность полученного вывода при помощи вычисления символа Лежандра по упрощенной методике. В случае если такая возможность есть – извлечь квадратный корень.
Пример решения.
| Дано: a = 26 p = 127 | Решение:
|
Найти: J(a, p)
Проверить:
по L(a, p)
при J(a, p) = 1 найти
| |
Проверка: 
Извлечение корней:
|