Алгоритм Чиполлы

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

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

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

Вход:

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

Выход:

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 }$.

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

${\displaystyle \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}}$

${\displaystyle =\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 }$.

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

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

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

${\displaystyle \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 }$.

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

${\displaystyle (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}$.

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

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

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

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

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

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

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

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

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

${\displaystyle 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}$.

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

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

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

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

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

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

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

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

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