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

В вычислительной теории чисел алгоритм Чиполлы представляет собой метод решения сравнения формы

$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$ и вычислив символ Лежандра $({\frac {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. Это можно вычислить с помощью критерия Эйлера : ${\textstyle (10|13)\equiv 10^{6}\equiv 1{\pmod {13}}.}$ Это подтверждает, что 10 является квадратом, и, следовательно, алгоритм можно применить.

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

$\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$. Действительно, ${\textstyle 6^{2}\equiv 10{\pmod {13}}.}$

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

Первая часть доказательства состоит в проверке того, что $\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}$. Фактически, это аддитивные обратные элементы x и y . За то, что показали, что каждый ненулевой элемент $\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(a^{2}-n\right)\right)+\left(x_{1}y_{2}+y_{1}x_{2}\right)\omega =1$.

Итак, два равенства $x_{1}x_{2}+y_{1}y_{2}(a^{2}-n)=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(a^{2}-n\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}$,

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

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

Вторая и средняя часть доказательства показывает, что для каждого элемента $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 — количество единиц в этом представлении. Чтобы найти методом проб и ошибок, ожидаемое количество вычислений символа Лежандра равно 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(a+\omega \right)=\left(ad^{2}-b\left(x+d\right)\right)+\left(d^{2}-by\right)\omega ,$

где $d=(x+ya)$ и $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$.

Основные модули мощности

Согласно «Истории чисел» Диксона, следующая формула Чиполлы позволит найти квадратные корни по модулю степеней простых чисел:

$2^{-1}q^{t}((k+{\sqrt {k^{2}-q}})^{s}+(k-{\sqrt {k^{2}-q}})^{s}){\bmod {p^{\lambda }}}$

где $t=(p^{\lambda }-2p^{\lambda -1}+1)/2$ и $s=p^{\lambda -1}(p+1)/2$

где $q=10$, $k=2$ как в примере этой статьи

На примере статьи в вики мы видим, что приведенная выше формула действительно имеет квадратные корни по модулю простых степеней.

Как

${\sqrt {10}}{\bmod {13^{3}}}\equiv 1046$

Теперь решите $2^{-1}q^{t}$ с помощью:

$2^{-1}10^{(13^{3}-2\cdot 13^{2}+1)/2}{\bmod {13^{3}}}\equiv 1086$

Теперь создайте $(2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}$ и $(2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}$ (См. здесь код Mathematica, показывающий приведенное выше вычисление, помня что здесь происходит что-то близкое к сложной модульной арифметике)

Как таковой:

$(2+{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}\equiv 1540$ и $(2-{\sqrt {2^{2}-10}})^{13^{2}\cdot 7}{\bmod {13^{3}}}\equiv 1540$

и окончательное уравнение:

$1086(1540+1540){\bmod {13^{3}}}\equiv 1046$ какой ответ.

Источники

• Э. Бах, Алгоритмическая теория чисел Дж. О. Шаллита: эффективные алгоритмы, MIT Press, (1996)