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

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

$x^2\equiv n(\mathrm{mod}p),$

где $x,n\in {𝐅}_p$, так что n будет квадратом числа x, и где $p$ является нечётным простым числом. Здесь ${𝐅}_p$ обозначает конечное поле с $p$ элементами $\{0,1,\dots ,p-1\}$. Алгоритм носит имя итальянского математика Шаблон:Не переведено 5, открывшего метод в 1907.

Алгоритм

Вход:

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

Выход:

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

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

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

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

Пример

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

Прежде чем применять алгоритм, нужно проверить, что число $10$ является на самом деле квадратом в поле ${𝐅}_{13}$, что означает, что символ Лежандра $(10|13)$ должен быть равен 1. Проверить это можно с помощью критерия Эйлера: $(10|13)\equiv 10^6\equiv 1mod13$. Это подтверждает, что 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 -1mod13$. Таким образом, число $a=2$ подходит.
• Шаг 2: Вычисляем $x={(a+\sqrt{a^2-n})}^{(p+1)/2}={(2+\sqrt{-6})}^7.$

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

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

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

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

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

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

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

$(x_1+y_1\omega )+(x_2+y_2\omega )=(x_1+x_2)+(y_1+y_2)\omega$.

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

$(x_1+y_1\omega )(x_2+y_2\omega )=x_1{x}_2+x_1{y}_2\omega +y_1{x}_2\omega +y_1{y}_2{\omega }^2$

$=(x_1{x}_2+y_1{y}_2(a^2-n))+(x_1{y}_2+y_1{x}_2)\omega$.

Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле ${𝐅}_{p^2}$ похоже на поле комплексных чисел (где $\omega$ служит аналогом i).
Нейтральным элементом по сложению служит $0$ или, более формально, $0+0\omega$ — если $\alpha \in {𝐅}_{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 )=(x\cdot 1+0\cdot y(a^2-n))+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha$.

Осталось проверить только, что в ${𝐅}_{p^2}$ существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа $x+y\omega$ является число $-x-y\omega$, которое также содержится в поле ${𝐅}_{p^2}$, поскольку $-x,-y\in {𝐅}_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 )=(x_1{x}_2+y_1{y}_2(n^2-a))+(x_1{y}_2+y_1{x}_2)\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{(y_1(n^2-a)-x_1^2{y}_1^{-1})}^{-1}$,

$y_2={(y_1(n^2-a)-x_1^2{y}_1^{-1})}^{-1}$.

Обратные элементы в выражениях для $x_2$ и $y_2$ существуют, поскольку они являются элементами поля ${𝐅}_p$. Тем самым мы завершаем первую часть доказательства.

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

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

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

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

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

$x_0^2={(a+\omega )}^{p+1}=(a+\omega )(a+\omega {)}^p=(a+\omega )(a-\omega )=a^2-{\omega }^2=a^2-(a^2-n)=n$.

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

Скорость

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

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

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

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

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

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