Речь пойдёт о решении модулярного уравнения $$ x^2 = a \mod p $$ относительно $$ x $$ при простом $$ p \geq 3 $$ и произвольном значении параметра $$ a $$ (обычно на промежутке $$ 0 \leq a < p $$). По-другому можно сформулировать задачу таким образом, что необходимо найти такие $$ x $$, что их квадрат в остатке от деления на простое $$ p \geq 3 $$ даёт $$ a $$. Шаг за шагом будут разобраны не только известные связанные алгоритмы, но и математические рассуждения и теоремы, объясняющие справедливость и вырабатывающие необходимую интуицию. Число $$ p $$ выбирается простым, чтобы арифметика образовывала поле. Как мы ниже убедимся, это существенно влияет на ряд теорем. ### Модулярная запись Запись вида $$ a = b \mod m $$ читаеся как $$ a $$ сравнимо с $$ b $$ по модулю $$ m $$ и по определению означает, что разность чисел $$ a $$ и $$ b $$ делится на $$ m $$. Нетрудно доказать, что с обеими частями данного равенства можно делать все те же арифметические операции, что и в обычных тождествах: сложение, вычитание, умножение. Например, можно к обеим частям выражения добавить одно и то же число, либо домножить. Также к любой из частей всегда можно добавить слагаемое, кратное $$ m $$. Например, запись $$ 32 = 18 \mod 7 $$ является верной, поскольку и 32, и 18 дают один и тот же остаток от деления на 7 (он равен 4). Или, что то же самое, разность 32 и 18 делится на 7. ### Алгоритм Евклида Алгоритм Евклида - это метод нахождения НОД (наибольший общий делитель) для двух натуральных чисел. Он классически гласит: "вычитай из большего меньшее, пока числа не сравняются". Ниже мы строго докажем его справедливость. ### Лемма 1. Пара натуральных чисел $$ a,b $$, таких что $$ a>b $$, имеет те же делители, что и пара $$ (a-b),b $$. Если некоторое число $$ q $$ делит $$ a $$ и $$ b $$ (является общим делителем), то существуют такие натуральные $$ a' $$ и $$ b' $$, что $$ a=qa', b=qb' $$. Рассмотрим разность: $$ a-b = qa' - qb' = q(a'-b') $$ То есть $$ q $$ является делителем разности $$ (a-b) $$, что и требовалось доказать. Аналогично и в обратную сторону можно показать, что новые делители в паре $$ (a-b),b $$ не появляются по отношению к $$ a,b $$. То есть любой общий делитель в паре $$ (a-b),b $$ является общим делителем и для $$ a,b $$. ### Теорема 1. Алгоритм Евклида сходится к НОД. Следуя алгоритму Евклида, согласно **лемме 1**, множество делителей сохраняется для пары на каждом этапе. Ввиду вычитания, сумма элементов пары всегда строго уменьшается, следовательно, алгоритм рано или поздно достигнет либо нуля, либо равенства. Но очевидно, чтобы на каком-то шаге вычитание дало 0, пара должна состоять из одинаковых элементов, поэтому непосредственно перед нулём сработает критерий остановки на равенство элементов. Делители финального элемента полностью совпадают с общими делителями исходной пары. И так как у любого числа наибольший делитель есть само это число, то оно же и будет НОД для нашего случая. ### Определение взаимно простых чисел Два числа называются взаимно простыми, если их НОД равен 1. То есть они не имеют никаких общих делителей среди натуральных чисел кроме тривиального 1. ### Теорема 2 (соотношение Безу и расширенный алгоритм Евклида). Для любых взаимно простых натуральных $$ a,b $$ существуют целые $$ x,y $$, такие что $$ ax+by=1 $$. Так как числа $$ a,b $$ взаимно простые, то их НОД равен 1, поэтому алгоритм Евклида остановится на числе 1 (по **теореме 1**). Если мы на каждом этапе будем запоминать то, сколько раз мы прибавляли и вычитали $$ a $$ и $$ b $$, то в итоге и накопятся необходимые $$ x $$ и $$ y $$. Чтобы показать это формально, зададим состояние первого элемента в паре как $$ (x_1,y_1) $$, где $$ x_1 $$ показывает то, с каким коэффициентом входит число $$ a $$, а $$ y_1 $$ отвечает за число $$ b $$. Само же число в паре с состоянием $$ (x_1,y_1) $$ равно $$ x_1 a + y_1 b $$. Аналогично второму элементу в паре соответствует состояние $$ (x_2,y_2) $$ и само число равно $$ x_2 a + y_2 b $$. В самом начале непосредственно первому числу в паре соответствует состояние $$ (1,0) $$, так как в нём только число $$ a $$, а второму числу соответствует состояние $$ (0,1) $$. Далее мы повторяем следующую процедуру: 1. Если $$ x_1 a + y_1 b > x_2 a + y_2 b $$, то: $$ (x_1,y_1) \to (x_1-x_2,y_1-y_2) $$ 2. Если $$ x_1 a + y_1 b < x_2 a + y_2 b $$, то: $$ (x_2,y_2) \to (x_2-x_1,y_2-y_1) $$ 3. Если $$ x_1 a + y_1 b = x_2 a + y_2 b $$, то останавливаемся и берём $$ x=x_1, y=y_1 $$ за искомые коэффициенты в соотношении Безу. Так как равенство будет достигнуто на числе 1, то: $$ ax + by = 1 $$ Данная процедура называется расширенным алгоритмом Евклида. С практической точки зрения вместо многократных разностей в паре эффективнее вычислять остаток от деления. Например, если на каком-то этапе есть пара $$ u,v $$, где $$ u>v $$, то произвести деление с остатком, представив $$ u = qv + r $$, далее сразу делаем корректировку состояния $$ (x_1,y_1) \to (x_1-qx_2,y_1-qy_2) $$. Это позволяет за одну итерацию произвести сразу $$ q $$ соответствующих вычитаний в подходе, описанном выше. На практике данный алгоритм является очень эффективным для нахождения обратного элемента в мультипликативной (по умножению) группе кольца вычетов с простым модулем. ### Лемма 2. Если есть равенство $$ au = bv $$, где $$ a,b $$ взаимно простые, то $$ b $$ - делитель $$ u $$ и $$ a $$ - делитель $$ v $$. Так как $$ a,b $$ взаимно простые, то согласно соотношению Безу (**теорема 2**) существуют целые $$ x,y $$, такие что: $$ ax + by = 1 $$ Домножим обе части на $$ u $$ и применим равенство $$ au = bv $$, вынося общий множитель: $$ aux + buy = u $$ $$ bvx + buy = u $$ $$ b (vx + uy) = u $$ Поэтому $$ b $$ - делитель $$ u $$. Симметрично и $$ a $$ - делитель $$ v $$. ### Теорема 3. Если простое $$ p $$ делит $$ ab $$, то $$ p $$ делит либо $$ a $$, либо $$ b $$. В другой формулировке можно записать теорему как: $$ ab = 0 \mod p \implies (a = 0 \mod p) \lor (b = 0 \mod p) $$ Достаточно доказать, что если $$ p $$ - не делитель $$ a $$, то тогда $$ p $$ - делитель $$ b $$. Так как $$ p $$ простое, то раз $$ p $$ - не делитель $$ a $$, единственным общим делителем в паре $$ a,p $$ остаётся 1, стало быть $$ a,p $$ взаимно просты. С другой стороны, раз $$ p $$ делит $$ ab $$, то существует такое $$ q $$, что $$ ab = pq $$. Сославшись на **лемму 2**, так как $$ a,p $$ взаимно просты, $$ b $$ будет делиться на $$ p $$. Есть и другой способ это обосновать. Данный факт следует из основной теоремы арифметики. Если произведение $$ ab $$ делится на простое $$ p $$, то оно присутствует в разложении на простые множители и может быть отнесено либо к $$ a $$, либо к $$ b $$. ### Теорема 4 (малая теорема Ферма). Для любого простого $$ p $$ и произвольного $$ a \neq 0 \mod p $$ выполняется $$ a^{p-1} = 1 \mod p $$. Чтобы это доказать, рассмотрим множество всех ненулевых остатков $$ \{ 1,2,3,...,(p-1) \} $$. Если каждый из них домножить на произвольное $$ a \neq 0 \mod p $$, то получим множество $$ \{ a,2a,3a,...,(p-1)a \} $$, которое будет являться перестановкой изначального. Действительно, если предположить, что это не так и у нас для каких-то различных остатков $$ m $$ и $$ n $$ домножение на $$ a $$ привело к одному и тому же, то есть выполнилось $$ ma = na \mod p $$, то тогда мы можем это выражение привести к виду $$ (m-n) a = 0 \mod p $$. И так как $$ a \neq 0 \mod p $$, то по **теореме 3** обязательно должно быть $$ m=n $$ - противоречие. Перемножив все элементы, получаем: $$ a \cdot 2a \cdot 3a \cdot ... \cdot (p-1)a = 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \mod p $$ $$ a^{p-1} (1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1)) = 1 \cdot 2 \cdot 3 \cdot ... \cdot (p-1) \mod p $$ Так как $$ p $$ простое, то произведение всех ненулевых остатков взаимно просто с $$ p $$. Следовательно: $$ a^{p-1} = 1 \mod p $$ Данный факт можно понять и другим способом. Можно взять произвольное $$ a \neq 0 \mod p $$ и начать с числа $$ b_1 = 1 $$, выстраивая последовательность $$ b_1, b_1 a, b_1 a^2, b_1 a^3 ... $$. Во-первых, так как $$ p $$ простое, мы никогда не придём в $$ 0 $$. Во-вторых, так как количество остатков ограничено мы рано или поздно придём к $$ b_1 $$. Мы не можем пропустить $$ b_1 $$ и прийти к некоторому $$ b_1 a^m $$, поскольку это бы означало, что мы пришли к этому числу из разных $$ x $$ и $$ y $$ путём домножения на $$ a $$. То есть $$ ax = ay \mod p $$ или $$ a(x-y) = 0 \mod p $$, что невозможно, если $$ x \neq y \mod p $$. Предположим, что мы пришли к $$ b_1 $$ на шаге под номером $$ d $$. Тогда мы имеем: $$ b_1 a^d = b_1 \mod p $$ Вспомним, что мы полагали $$ b_1 = 1 $$: $$ a^d = 1 \mod p $$ Если мы посетили все элементы в последовательности, то очевидно $$ d = p-1 $$, что и требовалось доказать. Но если нет, то существует некоторый элемент $$ b_2 $$, который оказался пропущен. Начнём выстраивать последовательность от него: $$ b_2, b_2 a, b_2 a^2, b_2 a^3 ... $$. Мы точно так же придём в $$ b_2 $$ на шаге под номером $$ d $$, поскольку $$ a^d = 1 \mod p $$. Прийти ни в какой элемент предыдущей последовательности мы не сможем. А также у нас нет возможности прийти в $$ b_2 $$ на шаге раньше, чем $$ d $$. Если допустить, что мы пришли в $$ b_2 $$ на шаге $$ k < d $$, то $$ b_2 a^k = b_2 \mod p $$ или $$ b_2 (a^k - 1) = 0 \mod p $$, из чего сразу следует, что $$ a^k = 1 \mod p $$, что означало бы, что мы должны были прийти к $$ 1 $$ в первоначальной последовательности на шаге $$ k $$, который раньше, чем $$ d $$. В итоге мы проходим ещё $$ d $$ элементов, не пересекающихся с первоначальной последовательностью от $$ b_1 $$. Далее, если у нас ещё остались непройденные элементы, можно выбрать $$ b_3 $$ и аналогично строить от него последовательность, получив ещё $$ d $$ новых элементов. И так далее, пока не посетим все $$ (p-1) $$ ненулевых остатков. Заметим, что мы таким образом доказали, что $$ d $$ является делителем $$ (p-1) $$, поэтому: $$ a^{p-1} = 1 \mod p $$ ### Теорема 5. Если уравнение вида $$ x^2 = a \mod p $$, где $$ p \geq 3 $$ простое, имеет решение, то их ровно два различных, причём $$ x_1 + x_2 = 0 \mod p $$. Допустим, $$ x_1 $$ является решением. Тогда очевидно, что $$ x_2 = -x_1 \mod p $$ также является решением. Они не могут совпадать, так как простое $$ p $$ нечётно согласно условию. Докажем теперь, что нет другой пары $$ y_1,y_2 $$, которые удовлетворяли бы такому же уравнению (обозначим за $$ y $$). От противного: $$ \begin{cases} x^2 = a \mod p \\ y^2 = a \mod p \\ \end{cases} $$ Вычтем: $$ x^2 - y^2 = 0 \mod p $$ $$ (x-y)(x+y) = 0 \mod p $$ То есть либо $$ x = y \mod p $$, либо $$ x = -y \mod p $$, что означает, что пара $$ y_1,y_2 $$ совпадает с $$ x_1,x_2 $$ либо прямо, либо с перестановкой. ### Определение квадратичного вычета и невычета Если уравнение $$ x^2 = a \mod p $$ имеет решение, то $$ a $$ называется квадратичным вычетом. В противном случае - квадратичным невычетом. ### Лемма 3. Для простого $$ p \geq 3 $$ количество квадратичных вычетов и невычетов равны между собой и числу $$ \frac{p-1}{2} $$. Как было показано в **теореме 5**, пара $$ x,(-x) $$ отображается в единственный для них $$ a = x^2 \mod p $$, называемый квадратичным вычетом. Следовательно, количество вычетов составляет половину от общего числа ненулевых остатков, то есть $$ \frac{p-1}{2} $$. Оставшихся невычетов такое же количество: $$ (p-1) - \frac{p-1}{2} = \frac{p-1}{2} $$. ### Теорема 6. Многочлен n-й степени может иметь максимум n корней. Любой многочлен можно представить в виде произведения неприводимых многочленов (неприводимые многочлены - это те, которые уже нельзя представить в виде какого-либо произведения многочленов более младших степеней). Среди них могут быть многочлены первой степени - вида $$ (x-x_i) $$, которые, согласно **теореме 3**, соответствуют корням $$ x_i $$. У многочлена n-й степени максимум может быть n линейных множителей, которые соответствуют n корням. Корни могут быть как кратными (встречаться несколько раз как одинаковые линейные множители), так и полностью различными. ### Теорема 7. Справедливо разложение: $$ x^{p-1} - 1 = (x-1)(x-2)...(x-(p-1)) \mod p $$ Согласно малой теореме Ферма (**теорема 4**) для любого $$ x \neq 0 \mod p $$ справедливо равенство: $$ x^{p-1} = 1 \mod p $$ Его можно переписать как уравнение на многочлен: $$ x^{p-1} - 1 = 0 \mod p $$ Так как данное равенство справедливо для всех $$ x $$, а количество возможных $$ x $$ равно $$ (p-1) $$ (как количество всех ненулевых остатков), что равно старшей степени многочлена, то он очевидно разлагаеся в произведение линейных многочленов, соответствующих каждому ненулевому остатку от $$ 1 $$ до $$ (p-1) $$: $$ x^{p-1} - 1 = (x-1)(x-2)...(x-(p-1)) \mod p $$ ### Символ Лежандра Символом Лежандра $$ L(a) $$ называется: $$ L(a) = \begin{cases} 0, a = 0 \mod p \\ 1, a^{\frac{p-1}{2}} = 1 \mod p \\ -1, a^{\frac{p-1}{2}} = -1 \mod p \\ \end{cases} $$ Если $$ a \neq 0 \mod p $$, то выражение $$ a^{\frac{p-1}{2}} $$ может принимать только значения $$ \pm 1 \mod p $$, потому что согласно малой теореме Ферма (**теорема 4**): $$ a^{p-1} = 1 \mod p $$ $$ \left( a^{\frac{p-1}{2}} \right)^2 = 1 \mod p $$ А уравнение $$ x^2 = 1 \mod p $$ имеет только два решения $$ x = \pm 1 \mod p $$, используя результат **теоремы 5**. ### Теорема 8. Среди ненулевых остатков количество элементов с символом Лежандра 1 равно количеству элементов с символом Лежандра -1 (их число $$ \frac{p-1}{2} $$ для каждого). Так как $$ (p-1) $$ чётно при простом $$ p \geq 3 $$, то мы можем сделать следующее разложение многочлена $$ x^{p-1}-1 $$, содержащего все ненулевые остатки: $$ x^{p-1}-1 = (x^{\frac{p-1}{2}} - 1)(x^{\frac{p-1}{2}} + 1) \mod p $$ Каждый из множителей $$ (x^{\frac{p-1}{2}} - 1) $$ и $$ (x^{\frac{p-1}{2}} + 1) $$ содержит свой набор корней в количестве по $$ \frac{p-1}{2} $$ (по **теореме 6**). Корни не повторяются, так как исходный многочлен содержит неповторяющиеся корни (по **теореме 7**). Величина $$ x^{\frac{p-1}{2}} $$ является символом Лежандра для каждого корня $$ x $$ (по модулю $$ p $$), следовательно, первому множителю $$ (x^{\frac{p-1}{2}} - 1) $$ соответствуют такие $$ x $$, для которых символ Лежандра равен 1, а для множителя $$ (x^{\frac{p-1}{2}} + 1) $$ имеем символ Лежандра -1. ### Теорема 9. Символ Лежандра произведения равен произведению символов Лежандра. То есть нужно доказать: $$ L(ab) = L(a) \cdot L(b) $$. $$ L(ab) = (ab)^{\frac{p-1}{2}} \mod p = a^{\frac{p-1}{2}} \cdot b^{\frac{p-1}{2}} \mod p = L(a) \cdot L(b) $$ ### Теорема 10. Для квадратичного вычета символ Лежандра равен $$ 1 $$, а для невычета $$ -1 $$. Если $$ a $$ квадратичный вычет, то существует $$ x $$, такой что $$ x^2 = a \mod p $$. Следовательно (используя **теорему 9**): $$ L(a) = L(x^2) = L(x) \cdot L(x) = 1 $$ Так как по **лемме 3** у нас квадратичных вычетов всего $$ \frac{p-1}{2} $$ и ровно столько же элементов, соответствующих символу Лежандра 1 (по **теореме 8**), мы можем сделать вывод, что символ Лежандра 1 соответствует квадратичному вычету, а символ -1 соответствует невычету. ### Ранг элемента Простое число $$ p \geq 3 $$ всегда можно единственным образом разложить до вида $$ p - 1 = 2^s \cdot q $$, где $$ s \geq 1 $$ и $$ q $$ - нечётно. Согласно малой теореме Ферма (**теорема 4**), для любого $$ a \neq 0 \mod p $$ справедливо $$ a^{2^s q} = 1 \mod p $$. Назовём рангом элемента $$ a $$ такое минимальное число $$ r $$, что $$ a^{2^r q} = 1 \mod p $$. Очевидно, что $$ 0 \leq r \leq s $$. Обозначим ранг элемента $$ a $$ как $$ R(a) $$. По своему смыслу ранг элемента $$ a $$ - это минимальное количество раз, которое нужно возвести число $$ a^q $$ в квадрат, чтобы получить $$ 1 $$. ### Лемма 4. Ранг невычета равен $$ s $$. Невычету $$ a $$ соответствует символ Лежандра $$ a^{\frac{p-1}{2}} = -1 \mod p $$, что можно переписать как $$ a^{2^{s-1} q} = -1 \mod p $$. Из этого следует, что ранг не равен $$ (s-1) $$, поэтому он равен единственно возможному оставшемуся значению $$ s $$, гарантированному малой теоремой Ферма (**теорема 4**). ### Лемма 5. При возведении в квадрат ранг уменьшается на 1 (для ранга больше 0). По определению ранга $$ a $$ имеем: $$ a^{2^{R(a)} q} = 1 \mod p $$ $$ a^{2^{R(a) - 1} q} \neq 1 \mod p $$ Выделим $$ a^2 $$ из выражений, что легко сделать, так как в показателе находится степень $$ 2 $$: $$ (a^2)^{2^{R(a)-1} q} = 1 \mod p $$ $$ (a^2)^{2^{R(a) - 2} q} \neq 1 \mod p, R(a) \geq 2 $$ Это и означает, что ранг элемента $$ a^2 $$ равен $$ R(a) - 1 $$. Получаем: $$ R(a^2) = R(a) - 1 $$ ### Лемма 6. Степень перед рангом (больше 0) равна -1. То есть нужно доказать $$ a^{2^{R(a) - 1} q} = -1 \mod p $$. Так как $$ R(a) > 0 $$, то мы можем сделать следующее: $$ a^{2^{R(a)}q} = 1 \mod p $$ $$ \left( a^{2^{R(a)-1}q} \right)^2 = 1 \mod p $$ Данное уравнение относительно $$ a^{2^{R(a)-1}q} $$ должно иметь два решения $$ \pm 1 \mod p $$ (**теорема 5**), но решение $$ 1 $$ не подходит, потому что иначе ранг был бы ниже $$ R(a) $$. Следовательно: $$ a^{2^{R(a)-1}q} = -1 \mod p $$ ### Лемма 7. Если элементы имеют одинаковый ранг (больше 0), то ранг их произведения будет меньше. То есть нужно доказать $$ R(a) = R(b) > 0 \implies R(ab) < R(a) $$. Для этого воспользуемся результатами **леммы 6**, согласно которой: $$ \begin{cases} a^{2^{R(a)-1}q} = -1 \mod p \\ b^{2^{R(b)-1}q} = -1 \mod p \\ \end{cases} $$ Перемножим левые и правые части: $$ (ab)^{2^{R(a)-1}q} = 1 \mod p $$ Из этого следует, что ранг $$ ab $$ меньше либо равен $$ R(a) - 1 $$ или другими словами: $$ R(ab) < R(a) $$ ### Лемма 8. Если ранг $$ a $$ равен 0, то уравнение $$ x^2 = a \mod p $$ имеет решения $$ \pm a^{\frac{q+1}{2}} \mod p $$. Если $$ R(a) = 0 $$, то мы имеем: $$ a^q = 1 \mod p $$ Домножим уравнение $$ x^2 = a \mod p $$ на $$ a^q $$ справа, так как это $$ 1 \mod p $$: $$ x^2 = a^{q+1} \mod p $$ $$ (q+1) $$ чётно, следовательно: $$ x = \pm a^{\frac{q+1}{2}} \mod p $$ ### Теорема 11. Если простое число $$ p = 3 \mod 4 $$, то уравнение $$ x^2 = a \mod p $$ имеет решения $$ x = \pm a^{\frac{p+1}{4}} \mod p $$ (если $$ a $$ является квадратичным вычетом). Если простое $$ p = 3 \mod 4 $$, то справедливо разложение $$ p-1 = 2q $$, где $$ q $$ - нечётное. Это равносильно случаю $$ s=1 $$, следовательно, ранг любого элемента может быть равен 0 или 1, причём ранг 1 соответствует невычету, для случая которого уравнение $$ x^2 = a \mod p $$ не будет иметь решений. Стало быть, если уравнение имеет решения, то ранг $$ a $$ должен быть 0, что позволяет нам воспользоваться **леммой 8**: $$ x = \pm a^{\frac{q+1}{2}} \mod p = \pm a^{\frac{p+1}{4}} \mod p $$ ### Решение уравнения $$ x^2 = a \mod p $$ для простого $$ p \geq 3 $$ в общем виде Предварительно необходимо проверить, что $$ a $$ является квадратичным вычетом, потому что в противном случае решений нет. Должно выполняться: $$ L(a) = a^{\frac{p-1}{2}} \mod p = 1 \mod p $$ Далее, если простое $$ p = 3 \mod 4 $$, то можно существенно сэкономить в вычислениях и взять результат **теоремы 11**: $$ x = \pm a^{\frac{p+1}{4}} \mod p $$ Для оставшегося случая $$ p = 1 \mod 4 $$ действуем следующим образом. Определяем $$ s $$ и нечётное $$ q $$ из разложения: $$ p - 1 = 2^s \cdot q $$. Берём произвольный невычет $$ z $$, его ранг равен $$ s $$ по **лемме 4**. Сначала вычисляем ранг числа $$ a $$, который равен некоторому $$ r_1 $$. Если $$ r_1 = 0 $$, то ответ будет $$ x = \pm a^{\frac{q+1}{2}} \mod p $$ (по **лемме 8**). В противном случае приготавливаем число с рангом $$ r_1 $$ из числа $$ z $$ возведением в степень $$ 2^{s-r_1} $$ (ранг будет контролируемо уменьшаться, согласно **лемме 5** от $$ s $$ до требуемого $$ r_1 $$) обозначенным как $$ c_1^2 $$: $$ c_1^2 = z^{2^{s-r_1}} $$ Домножим на него обе части уравнения: $$ (c_1 x)^2 = c_1^2 a \mod p $$ Ранг элемента $$ c_1^2 a $$ равен $$ r_2 < r_1 $$ (по **лемме 7**). Если $$ r_2 = 0 $$, то заканчиваем процедуру и получаем (по **лемме 8**) $$ c_1 x = \pm (c_1^2 a)^{\frac{q+1}{2}} \mod p \implies x = \pm c_1^q a^{\frac{q+1}{2}} \mod p $$. В противном случае продолжаем процедуру, построив $$ c_2,c_3... $$. В итоге на каком-то шаге под номером $$ K $$ мы получим нулевой ранг для $$ (c_1 c_2 ... c_K)^2 a $$, что даёт нам решение: $$ x = \pm (c_1 c_2 ... c_K)^q a^{\frac{q+1}{2}} \mod p $$ Данная процедура с небольшой оптимизацией известна в науке как алгоритм Тонелли-Шенкса.