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

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

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

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

Помимо простых модулей, алгоритм Чиполлы также способен извлекать квадратные корни по модулю простых степеней. ^[1]

Алгоритм

Входные данные:

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

Выходы:

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

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

Шаг 2 — вычислить x , вычислив внутри расширения поля . Этот 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}})}$ ${\displaystyle x^{2}=n.}$

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

Пример

(Примечание: все элементы до шага два рассматриваются как элементы , а все элементы на шаге два рассматриваются как элементы .) ${\displaystyle \mathbf {F} _{13}}$ ${\displaystyle \mathbf {F} _{13^{2}}}$

Найдите все x такие, что ${\displaystyle x^{2}=10.}$

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

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

${\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}$ ${\textstyle 6^{2}\equiv 10{\pmod {13}}.}$

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

Первая часть доказательства заключается в проверке того, что действительно является полем. Для простоты обозначений определяется как . Конечно, является квадратичным невычетом, поэтому в нет квадратного корня . Это можно грубо рассматривать как аналог комплексного числа i . Арифметика поля вполне очевидна. Сложение определяется как ${\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 }$

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

Теперь нужно проверить свойства поля. Свойства замкнутости относительно сложения и умножения, ассоциативности , коммутативности и дистрибутивности легко увидеть. Это потому, что в этом случае поле несколько напоминает поле комплексных чисел (при этом являясь аналогом i ). Аддитивное тождество равно , или более формально : Пусть , тогда ${\displaystyle \mathbf {F} _{p^{2}}}$ ${\displaystyle \omega }$
${\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 }$.

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

Итак, должны выполняться два равенства и . Детализация дает выражения для и , а именно ${\displaystyle x_{1}x_{2}+y_{1}y_{2}(a^{2}-n)=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(a^{2}-n\right)-x_{1}^{2}y_{1}^{-1}\right)^{-1}}$,

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

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

Вторая и средняя часть доказательства показывает, что для каждого элемента . По определению, не является квадратом в . Критерий Эйлера тогда говорит, что ${\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}$.

Таким образом . Это, вместе с малой теоремой Ферма (которая гласит, что для всех ) и знанием того, что в полях характеристики p уравнение выполняется, соотношение, иногда называемое мечтой первокурсника , показывает желаемый результат ${\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}$.

Обратите внимание, что это вычисление произошло в , так что это . Но с теоремой Лагранжа , утверждающей, что ненулевой многочлен степени n имеет не более n корней в любом поле K , и знанием того, что имеет 2 корня в , эти корни должны быть всеми корнями в . Только что было показано, что и являются корнями в , так что должно быть так, что . ^[3] ${\displaystyle \mathbf {F} _{p^{2}}}$ ${\displaystyle x_{0}\in \mathbf {F} _{p^{2}}}$ ${\displaystyle x^{2}-n}$ ${\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}}$

Скорость

После нахождения подходящего a число операций, необходимых для алгоритма, равно умножениям, суммам, где m — число цифр в двоичном представлении p , а k — число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Но может повезти с первой попыткой, и может потребоваться больше 2 попыток. В поле выполняются следующие два равенства ${\displaystyle 4m+2k-4}$ ${\displaystyle 4m-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 ,}$

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

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

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

Предполагая, что (в случае , прямое вычисление намного быстрее) двоичное выражение имеет цифры, из которых k — единицы. Таким образом, для вычисления степени , первую формулу нужно использовать раз, а вторую раз. ${\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}$ ${\displaystyle (p+1)/2}$ ${\displaystyle \left(a+\omega \right)}$ ${\displaystyle n-k-1}$ ${\displaystyle k-1}$

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

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

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

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

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

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

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

Как

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

Теперь решим через: ${\displaystyle 2^{-1}q^{t}}$

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

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

Как таковой:

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

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

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

Ссылки

1. Диксон, Леонард Юджин (1919). История теории чисел. Т. 1. С. 218.
2. Р. Крэндалл, К. Померанс Простые числа: вычислительная перспектива Springer-Verlag, (2001) стр. 157
3. "Алгоритм М. Бейкера Чиполлы для нахождения квадратных корней mod p" (PDF) . Архивировано из оригинала (PDF) 2017-03-25 . Получено 2011-08-24 .
4. Tornaría, Gonzalo (2002). "Квадратные корни по модулю P". LATIN 2002: Теоретическая информатика . Конспект лекций по информатике. Том 2286. С. 430–434. doi :10.1007/3-540-45995-2_38. ISBN 978-3-540-43400-9.
5. "История теории чисел" Том 1 Леонарда Юджина Диксона, стр. 218, Chelsea Publishing 1952 читать онлайн
6. Мишель Чиполла, Rendiconto dell' Accademia delle Scienze Fisiche e Matematiche. Наполи, (3), 10.1904, 144–150

Источники

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