Квадратные сравнения

Сейчас мы рассмотрим квадратные сравнения по простому нечётному модулю. Далее на протяжении всего раздела этот модуль мы будем обозначать буквой \(p\).

Поскольку \(p\) нечётный, то любое квадратное сравнение можно записать в виде

\[ x^2 + 2ax + c \equiv_p 0 \]

и заменой \(y=x+a\) привести к виду

\[ y^2 \equiv_p d \]

Поэтому без ограничения общности будем рассматривать задачу извлечения квадратного корня

\[ x^2 = a \]

Количество решений квадратного сравения

Если \(a\equiv_p 0\), то сравнение \(x^2 \equiv_p 0\) эквивалентно \(x\equiv_p 0\):

• если \(x\equiv_p 0\), то оба сравнения верны
• если \(x\) не кратно \(p\), то обе части первого сравнения можно на этот \(x\) сократить, получив второе сравнение и заодно — противоречие, из которого следует всё, что угодно

Если же \(a\) не кратно \(p\), то у сравнения либо 0 решений, либо 2: если \(X\) — какое-то решение, то сравнение можно переписать как

\[ x^2 \equiv_p X^2 \]

что эквивалентно

\[ (x-X)(x+X) \equiv_p 0 \]

откуда легко следует \(x\equiv_p \pm X\). Из-за того, что \(p\) нечётно, решения \(+X\) и \(-X\) различны.

Распределение точных квадратов

Будем говорить, что \(a\) является квадратным вычетом или точным квадратом по модулю \(p\), если \(a\) не кратно \(p\) и сравнение \(x^2\equiv_p a\) имеет решения.

Если мы возьмём все числа от \(1\) до \(p-1\) и каждое возведём в квадрат, то мы получим ровно \(\dfrac{p-1}{2}\) разных (по модулю \(p\)) результатов: каждый получен ровно два раза, как мы только что доказали.

Это означает, что ровно половина ненулевых остатков по модулю \(p\) являются точными квадратами.

Разрешимость квадратного сравнения

Формула Эйлера для простого \(p\) и \(x\), не кратного \(p\), имеет вид

\[ x^{p-1} \equiv_p 1 \]

(Кстати, в таком случае её называют малой теоремой Ферма.)

Поэтому, если

\[ a^{\frac{p-1}{2}} \not\equiv_p 1 \]

то сравнение \(x^2\equiv_p a\) не имеет решений.

Рассмотрим оставшийся случай

\[ a^{\frac{p-1}{2}} \equiv_p 1 \]

Все \(\dfrac{p-1}{2}\) точных квадратов относятся как раз к этому случаю. Более того, у сравнения

\[ y^k \equiv_p b \]

не может быть больше чем \(k\) различных решений, как мы несколько позже докажем. Поэтому ни один неквадрат в такую ситуацию не попадает.

Итого, при \(a\) не кратном \(p\) сравнимость \(a^{\frac{p-1}{2}}\) с единицей экивалентна разрешимости сравнения \(x^2 \equiv_p a\).

Замечание

Поскольку

\[ a^{p-1} - 1 = \left(a^{\frac{p-1}{2}}-1\right)\left(a^{\frac{p-1}{2}}+1\right) \]

то \(a^{\frac{p-1}{2}}\) при \(a\), не кратном \(p\), может быть сравнимо только с единицей или минус единицей.

Алгоритм Тонелли

Сейчас мы научимся решать квадратные сравнения.

Сперва заметим, что если \(p = 4k+3\), то \(x=a^{\frac{p+1}{4}}\) является решением сравнения \(x^2 \equiv_p a\), и никаких хитрых манипуляций производить не нужно.

Пусть \(p = 1 + q 2^s\), где \(q\) нечётно (а \(s>1\)).

Алгоритм Тонелли строит последовательность приближений к решению сравнения. Нулевое приближение определяется так:

\[ x_0 = a^{\frac{q+1}{2}} \]

Если \(a^q \equiv_p 1\), то \(x_0\) — решение. Если нет, то есть такой \(k\), что \(k\)-кратное возведение \(a^q\) в квадрат даст \(-1\):

• \(s\)-кратное возведение \(a^q\) в квадрат даёт единицу (согласно формуле Эйлера)
• единицу можно получить возведением в квадрат только из единицы и минус единицы

ВНИМАНИЕ это важнейшее соображение следует запомнить! Именно оно лежит в основе алгоритма быстрой генерации больших простых чисел.

Найдём теперь такой \(b_0\), что \(k\)-кратное возведение \(b_0^2\) в квадрат даст \(-1\) и выберем

\[ x_1 = b_0 x_0 \]

Заметим, что:

• \(x_1^2 \equiv_p (b_0^2 a^q) a\)
• \(k\)-кратное возведение \(b_0^2 a^q\) в квадрат даст 1

Поэтому либо \(b_0^2 a^q\) сравнимо с \(1\), либо же его нужно меньше чем \(k\) раз возводить в квадрат, чтобы получить минус единицу.

Итого на каждой итерации мы строим

\[ x_{m+1} = b_m x_m \]

выбирая \(b_m\) так, чтобы \(b_m^2\) для получения минус единицы нужно было бы столько же раз возводить в квадрат, сколько и

\[ (b_{m-1}b_{m-2}\ldots b_0)^2 a^q \]

Остался один маленький вопрос: а как искать \(b_i\)? Ответ, оказывается, очень прост: случайным образом найти любой неквадрат (их половина) \(z\). При возведении \(z^q\) в квадрат минус единицу даст лишь предпоследняя \((s-1)\)-я итерация. Поэтому среди результатов этих итераций мы всегда сможем отыскать нужную нам.

Дополнение: у многочлена не бывает много корней

Сейчас мы докажем, что у любого многочлена степени \(k\) не может быть больше \(k\) различных по модулю \(p\) корней.

Пусть это неверно, и есть многочлен, у которого корней больше, чем его степень.

Рассмотрим любой «плохой» многочлен \(Q\) с наименьшей (среди всевозможных «плохих») степенью, которую обозначим \(m\). Заметим сразу, что \(m\geqslant 1\).

Пусть \(Q(x_i)\equiv_p 0\) для всех \(i\) от \(0\) до \(m\). Тогда для всех \(i\) от \(1\) до \(m\) выполнено

\[ Q(x_i) - Q(x_0) \equiv_p 0 \]

Осталось заметить, что если

\[ Q = q_m x^m + \ldots + q_1 x + q_0 \]

то вышерассмотренные разности равны

\[ (x_i - x_0)\cdot ( q_m x_i^{m-1} + q_{m-1} x_0 x_i^{m-2} + \ldots ) \equiv_p 0 \]

откуда (в силу некратности \(p\) первых сомножителей левых частей) следует наличие у многочлена

\[ q_m x^{m-1} + q_{m-1} x_0 x^{m-2} + \ldots + q_1 x_0^{m-1} \]

не менее чем \(m\) различных решение, что противоречит предположению о минимальности \(m\).

PS Вообще говоря, доказать, что числа \(a\), для которых \((p-1)/2\)-я степень равна единице, являются вычетами, можно и не прибегая к рассуждению о количестве корней: достаточно заметить, что для таких чисел работает вышеизложенный алгоритм Тонелли.