Алгоритм Чиполлы (Glikjnmb Cnhklld)

Алгоритм Чиполлы — это техника решения конгруэнтного уравнения вида

$x^{2}\equiv n{\pmod {p}},$

где $x,n\in \mathbf {F} _{p}$, так что n будет квадратом числа x, и где $p$ является нечётным простым числом. Здесь $\mathbf {F} _{p}$ обозначает конечное поле с $p$ элементами $\{0,1,\dots ,p-1\}$. Алгоритм носит имя итальянского математика Микеле Чиполлы, открывшего метод в 1907.

Алгоритм

Вход:

• $p$, нечётное простое число,
• $n\in \mathbf {F} _{p}$, квадрат числа.

Выход:

• число $x\in \mathbf {F} _{p}$, удовлетворяющее равенству $x^{2}=n.$

Шаг 1. Находим число $a\in \mathbf {F} _{p}$, такое, что $a^{2}-n$ не является квадратом. Алгоритм для поиска таких чисел $a$ неизвестен, за исключением метода проб и ошибок. Просто выбираем какое-либо число $a$ и вычисляем символ Лежандра $(a^{2}-n|p)$, чтобы удостовериться, что $a$ удовлетворяет условию. Шанс, что случайное число $a$ подходит, равен $(p-1)/2p$. Если $p$ достаточно велико, эта величина примерно равна $1/2$. Таким образом, ожидаемое число попыток для получения подходящего a равно 2.

Шаг 2. Получаем x путём вычисления $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}$ в поле $\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})$. Это число x будет одним из корней уравнения $x^{2}=n.$

Если $x^{2}=n$, то $(-x)^{2}=n$ также выполняется. Поскольку p нечётно, $x\neq -x$, так что для найденного решения x всегда существует второе решение, равное -x.

Пример

(Замечание: Все элементы до второго шага принадлежат полю $\mathbf {F} _{13}$, а все элементы второго шага — полю $\mathbf {F} _{13^{2}}$). Ищем число x, такое, что $x^{2}=10.$

Прежде чем применять алгоритм, нужно проверить, что число $10$ является на самом деле квадратом в поле $\mathbf {F} _{13}$, что означает, что символ Лежандра $(10|13)$ должен быть равен 1. Проверить это можно с помощью критерия Эйлера: $(10|13)\equiv 10^{6}\equiv 1{\bmod {1}}3$. Это подтверждает, что 10 является квадратом и к нему можно применить алгоритм.

• Шаг 1: Находим число a, такое что $a^{2}-n$ не является квадратом. Как было указано выше, нужно использовать метод проб и ошибок. Выберем число $a=2$, для него $a^{2}-n$ буде равно 7. Символ Лежандра $(7|13)$ равен -1, что можно опять получить с помощью критерия Эйлера, $7^{6}=343^{2}\equiv 5^{2}\equiv 25\equiv -1{\bmod {1}}3$. Таким образом, число $a=2$ подходит.
• Шаг 2: Вычисляем $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\right)^{7}.$

$\left(2+{\sqrt {-6}}\right)^{2}=4+4{\sqrt {-6}}-6=-2+4{\sqrt {-6}}.$

$\left(2+{\sqrt {-6}}\right)^{4}=\left(-2+4{\sqrt {-6}}\right)^{2}=-1-3{\sqrt {-6}}.$

$\left(2+{\sqrt {-6}}\right)^{6}=\left(-2+4{\sqrt {-6}}\right)\left(-1-3{\sqrt {-6}}\right)=9+2{\sqrt {-6}}.$

$\left(2+{\sqrt {-6}}\right)^{7}=\left(9+2{\sqrt {-6}}\right)\left(2+{\sqrt {-6}}\right)=6.$

Таким образом, $x=6$ является решением, как и $x=-6{\bmod {1}}3=(-6+13){\bmod {1}}3=7.$ Действительно, $\ 6^{2}=36{\bmod {1}}3=10$ и $7^{2}=49{\bmod {1}}3=10.$

Доказательство

В первой части доказательства убедимся, что $\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})=\{x+y{\sqrt {a^{2}-n}}:x,y\in \mathbf {F} _{p}\}$ действительно является полем. Для простоты выкладок введём число $\omega$, равное ${\sqrt {a^{2}-n}}$. Конечно, $a^{2}-n$ не является квадратичным вычетом, так что квадратный корень не существует в $\mathbf {F} _{p}$. Это $\omega$, грубо говоря, можно рассматривать как аналог комплексного числа i. Арифметика поля вполне очевидна. Сложение определяется как

$\left(x_{1}+y_{1}\omega \right)+\left(x_{2}+y_{2}\omega \right)=\left(x_{1}+x_{2}\right)+\left(y_{1}+y_{2}\right)\omega$.

Умножение также определяется обычным путём. Если помнить, что $\omega ^{2}=a^{2}-n$, получим

$\left(x_{1}+y_{1}\omega \right)\left(x_{2}+y_{2}\omega \right)=x_{1}x_{2}+x_{1}y_{2}\omega +y_{1}x_{2}\omega +y_{1}y_{2}\omega ^{2}$

$=\left(x_{1}x_{2}+y_{1}y_{2}\left(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega$.

Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле $\mathbf {F} _{p^{2}}$ похоже на поле комплексных чисел (где $\omega$ служит аналогом i).
Нейтральным элементом по сложению служит $0$ или, более формально, $0+0\omega$ — если $\alpha \in \mathbf {F} _{p^{2}}$, то

$\alpha +0=(x+y\omega )+(0+0\omega )=(x+0)+(y+0)\omega =x+y\omega =\alpha$.

Нейтральным элементом по умножению служит $1$, точнее $1+0\omega$:

$\alpha \cdot 1=(x+y\omega )(1+0\omega )=\left(x\cdot 1+0\cdot y\left(a^{2}-n\right)\right)+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha$.

Осталось проверить только, что в $\mathbf {F} _{p^{2}}$ существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа $x+y\omega$ является число $-x-y\omega$, которое также содержится в поле $\mathbf {F} _{p^{2}}$, поскольку $-x,-y\in \mathbf {F} _{p}$. Чтобы показать, что любой ненулевой элемент $\alpha$ имеет обратный по умножению элемент, выпишем представления $\alpha =x_{1}+y_{1}\omega$ и $\alpha ^{-1}=x_{2}+y_{2}\omega$. Другими словами,

$(x_{1}+y_{1}\omega )(x_{2}+y_{2}\omega )=\left(x_{1}x_{2}+y_{1}y_{2}\left(n^{2}-a\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega =1$.

Получаем два уравнения, $x_{1}x_{2}+y_{1}y_{2}(n^{2}-a)=1$ и $x_{1}y_{2}+y_{1}x_{2}=0$. Решаем эту систему относительно $x_{2}$ и $y_{2}$, получим

$x_{2}=-y_{1}^{-1}x_{1}\left(y_{1}\left(n^{2}-a\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}$,

$y_{2}=\left(y_{1}\left(n^{2}-a\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}$.

Обратные элементы в выражениях для $x_{2}$ и $y_{2}$ существуют, поскольку они являются элементами поля $\mathbf {F} _{p}$. Тем самым мы завершаем первую часть доказательства.

Во второй части доказательства покажем, что для любого элемента $x+y\omega \in \mathbf {F} _{p^{2}}:(x+y\omega )^{p}=x-y\omega$. По определению $\omega ^{2}=a^{2}-n$ не является квадратом в $\mathbf {F} _{p}$. Тогда критерий Эйлера даёт

$\omega ^{p-1}=\left(\omega ^{2}\right)^{\frac {p-1}{2}}=-1$.

Таким образом, $\omega ^{p}=-\omega$. Это, вместе с малой теоремой Ферма (утверждающей, что $x^{p}=x$ для всех $x\in \mathbf {F} _{p}$) и знанием, что в полях с характеристикой $p$, выполняется равенство $\left(a+b\right)^{p}=a^{p}+b^{p}$, показывает желаемый результат

$(x+y\omega )^{p}=x^{p}+y^{p}\omega ^{p}=x-y\omega$.

Третья и последняя часть доказательства показывает, что в случае $x_{0}=\left(a+\omega \right)^{\frac {p+1}{2}}\in \mathbf {F} _{p^{2}}$ выполняется $x_{0}^{2}=n\in \mathbf {F} _{p}$.
Вычисляем

$x_{0}^{2}=\left(a+\omega \right)^{p+1}=(a+\omega )(a+\omega )^{p}=(a+\omega )(a-\omega )=a^{2}-\omega ^{2}=a^{2}-\left(a^{2}-n\right)=n$.

Заметим, что эти вычисления имеют место в $\mathbf {F} _{p^{2}}$, так что $x_{0}\in \mathbf {F} _{p^{2}}$. Теорема Лагранжа утверждает, что ненулевой многочлен степени n имеет не более n корней над полем K. Если учесть, что многочлен $x^{2}-n$ имеет 2 корня в $\mathbf {F} _{p}$, никаких других корней быть не может $\mathbf {F} _{p^{2}}$. Было показано, что $x_{0}$ и $-x_{0}$ являются корнями многочлена $x^{2}-n$ в $\mathbf {F} _{p^{2}}$, так что должно выполняться $x_{0},-x_{0}\in \mathbf {F} _{p}$.

Скорость

После нахождения подходящего a число операций, требуемых алгоритмом, составляет $4m+2k-4$ умножений и $4m-2$ сложений, где m — число знаков в двоичном представлении числа p, а k — число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Однако может посчастливиться с первого раза, но может потребоваться и более 2 попыток. В поле $\mathbf {F} _{p^{2}}$ выполняются следующие два равенства

$(x+y\omega )^{2}=\left(x^{2}+y^{2}\omega ^{2}\right)+\left(\left(x+y\right)^{2}-x^{2}-y^{2}\right)\omega ,$

где $\omega ^{2}=a^{2}-n$ заранее известно. Это вычисление требует 4 умножения и 4 сложения.

$\left(x+y\omega \right)^{2}\left(c+\omega \right)=\left(cd-b\left(x+d\right)\right)+\left(d^{2}-by\right)\omega ,$

где $d=(x+yc)$ and $b=ny$. Эта операция требует 6 умножений и 4 сложения.

Если предположить, что $p\equiv 1{\pmod {4}},$ (в случае $p\equiv 3{\pmod {4}}$, прямое вычисление $x\equiv \pm n^{\frac {p+1}{4}}$ много быстрее) двоичное выражение $(p+1)/2$ имеет $m-1$ знаков, из которых k равны единице. Таким образом, для вычисления $(p+1)/2$-ой степени числа $\left(a+\omega \right)$ первую формулу нужно применить $n-k-1$ раз, а вторую — $k-1$ раз.

Алгоритм Чиполлы лучше, чем алгоритм Тонелли — Шенкса тогда и только тогда, когда $S(S-1)>8m+20$, где $2^{S}$ максимальная степень 2, на которую делится $p-1$ .

Ссылки

• E. Bach, J.O. Shallit Algorithmic Number Theory: Efficient algorithms MIT Press, (1996)