Решение квадратичных сравнений по простому модулю.

<20 21 222324 25 26 >

Пусть дано сравнение x²≡a(mod p), p>2 – простое и .

Данное сравнение имеет 2 решения. Укажем, как найти эти решения.

Для p возможны следующие случаи:

p≡3(mod 4) p≡1(mod 4)

p≡5(mod 8) p≡1(mod 8)

p≡9(mod 16) p≡1(mod 16)

И т. д.

а)Пусть p≡3(mod 4), т.е. p=4k+3.

По критерию Эйлера, . Подставляя сюда p, получим

a^2k+1≡1(mod p)

a^2k+2≡a(mod p)

Вернувшись сравнению, которое требуется решить, заметим, что x²≡a²^k⁺²(mod p), и тогда x≡±a^k⁺¹(mod p) – искомое решение.

б) p≡5(mod 8), т.е. p=8k+5.

Найдем какой-нибудь квадратичный невычет по модулю p. Согласно св-ву 7 для символа Лежандра, таким невычетом в случае p=8k+5 будет являться «2». Тогда, согласо критерию Эйлера, 2⁴^k⁺²≡—1(mod p).

Так как a – квадратичный вычет по модулю p, то по критерию Эйлера, .

Тогда возможны два варианта: a²^k⁺¹≡1(mod p) или a²^k⁺¹≡—1(mod p).

В первом случае дальнейшие рассуждения проводим как в пункте а, и получаем x≡±a^k⁺¹(mod p).

Рассмотрим подробнее второй случай. Имеем:

a²^k⁺¹≡—1(mod p)

Для того, чтобы избавиться от знака (—) в правой части, домножим левую часть этого сравнения на 2⁴^k⁺², а левую – на –1.

2^4k+2a^2k+1≡1(mod p)

2^4k+2a^2k+2≡a(mod p)

x≡±2²^k⁺¹a^k⁺¹(mod p)

Таким образом, имеются два кандидата на решение:

x≡±a^k⁺¹(mod p).

x≡±2^2k+1a^k⁺¹(mod p)

Вычислив и подставив каждое из них в исходное сравнение, выберем ту пару, которая удовлетворяет исходному сравнению.

в) p≡9(mod 16), т.е. p=16k+9.

Найдем N – какой-нибудь квадратичный невычет по модулю p. Тогда по критерию Эйлера, .

С другой стороны, поскольку a – квадратичный вычет по модулю p, то по критерию Эйлера, .

Тогда возникают два случая: a⁴^k⁺²≡1(mod p) или a⁴^k⁺²≡-1(mod p).

Рассмотрим первый случай: a⁴^k⁺²≡1(mod p). Поскольку показатель степени в левой части сравнения – четный, то вновь возникают два варианта: a²^k⁺¹≡1(mod p) или a²^k⁺¹≡—1(mod p), первый из которых приводит, как ранее, к кандидату в решение x≡±a^k⁺¹(mod p), а второй вариант, рассуждая как в пункте б, приведем к кандидату в решения x≡±N⁴^k⁺²a^k⁺¹(mod p).

Рассмотрим второй случай: a⁴^k⁺²≡-1(mod p). Для того, чтобы избавиться от знака (—) в правой части сравнения, домножим правую часть на N⁸^k⁺⁴, а левую – на –1. Получим N⁸^k⁺⁴a⁴^k⁺²≡1(mod p). Поскольку показатели степеней в левой части получившегося сравнения четны, то отсюда возникают два варианта: N⁴^k⁺²a²^k⁺¹≡1(mod p) или N⁴^k⁺²a²^k⁺¹≡-1(mod p).

Рассмотрим первый из вариантов:

N⁴^k⁺²a²^k⁺¹≡1(mod p)

N^4k+2a^2k+2≡a(mod p)

x≡±N^2k+1a^k⁺¹(mod p).

Рассмотрим второй из вариантов:

N⁴^k⁺²a²^k⁺¹≡-1(mod p)

N^12k+6a^2k+1≡1(mod p)

N^12k+6a^2k+2≡a(mod p)

x≡±N⁶^k⁺³a^k⁺¹(mod p)

Итак, получили четыре пары – кандидата на решение:

x≡±a^k⁺¹(mod p)

x≡±N^2k+1a^k⁺¹(mod p)

x≡±N^4k+2a^k⁺¹(mod p)

x≡±N^6k+3a^k⁺¹(mod p)

Вычислив и подставив в исходное сравнение, выберем ту пару, которая удовлетворяет исходному сравнению.

Рассмотренным способом можно построить решение для любого простого модуля p. Если p=2^hk+2^h^—1+1, то при решении сравнения возникнет 2^h^—2 пар – кандидатов в решение, каждая из которых будет иметь вид x≡±N^z⁽²^k⁺¹⁾a^k⁺¹(mod p), где .

Главная проблема здесь – отыскание квадратичного невычета N, но поскольку, как было доказано ранее, квадратичных вычетов и невычетов по простому модулю – одинаковое количество, то невычет обязательно найдется.

Пример:

Решить сравнение x²≡8(mod 17).

17 – простое число. Выясним, имеет ли данное сравнение решение:

. Сравнение имеет 2 решения. Отыщем их.