Определение Множество натуральных чисел

Решение сравнений для случаев простого модуля.

, где число р не делится на 2 и простое и целое число a не делится на р.
Для того чтобы сравнение было разрешимо необходимо и достаточно, чтобы символ Лежандра был равен 1, тогда сравнение имеет ровно 2 решения.
Пуст p 3 (mod 4), то есть p=4m+ 3, где m Z. Разрешимость сравнения означает, что = 1. По свойству 3 символа Лежандра 1 = .
= ∙a (mod р). Таким образом, решение имеет вид (mod р).

Пусть р 5 (mod 8), то есть р = 8m + 5, где m Z. Разрешимость сравнения означает, что = 1. По свойству 3 символа Лежандра

1 = (mod p)= . Отсюда (mod p) или (mod p). В первом случае, умножая обе части сравнения на a, получаем (mod p) (mod р), то есть решение имеет вид (mod р).
При (mod p) ситуация немного сложнее. Заметим, что при р 5 (mod 8) число 2 является квадратичным невычетом по модулю р. Действительно, |. По свойству 3 символа Лежандра (mod р). Таким образом, (mod р). Тогда
∙
Умножая обе части этого сравнения на a, получаем решение срав­нения (mod р).
Здесь вместо числа 2 можно брать любой другой квадратичный невычет по модулю р.
Пусть p 1 (mod 8). Представим р в виде р = 2^k∙h + 1, где k≥З, число h нечетное. Разрешимость сравнения означает, что = 1.
По свойству 3 символа Лежандра 1 = . Отсюда Пусть N — произвольный квадратичный невычет по модулю p, то есть -1 = (mod р). Тогда при некотором целом S₂≥0 получим (mod р), откуда (mod р). Далее, при некотором целом S₃≥0 получим (mod р), откуда (mod р) и т.д. Получив сравнение
(mod р) для некоторого целого ≥ 0 и умножив обе его части на а, получаем решение (mod р).
Алгоритм 2.2. Решение сравнения второй степени по модулю простого числа [4].
Вход: Простое число р≠2; такие целые числа a, N, что
Выход: Решение сравнения .

1. 
   Представить число р в виде р = 2^k • h + 1, где число h нечетное.
   

2. 
   Положить a₁← (mod p), a₂← (mod p), (mod p), j←0.
   
3. 
   Для i = 0,1, ...,k-2 выполнять следующие действия.
   

1. 
   Положить b←a₁N₂ (mod p).
   
2. 
   Вычислить c←a₂b²(mod p).
   
3. 
   Вычислить абсолютно наименьший вычет d← (mod p). При d=1 положить j_i←0, при d=-1 положить j_i←1.
   
4. 
   Положить N₂ ← N₂ (mod р).
   

4. Результат:
Сложность этого алгоритма равна O(log⁴p).