Алгоритм Чиполлы — это техника решения конгруэнтного уравнения вида
![{\displaystyle x^{2}\equiv n{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/836ed66ff9f373e1ae182fb8e3cf65913d8efca2)
где
, так что n будет квадратом числа x, и где
является нечётным простым числом. Здесь
обозначает конечное поле с
элементами
. Алгоритм носит имя итальянского математика Микеле Чиполлы[англ.], открывшего метод в 1907.
Вход:
, нечётное простое число,
, квадрат числа.
Выход:
- число
, удовлетворяющее равенству ![{\displaystyle x^{2}=n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4533df866cc1d03d853742f9ca68b4498e08e460)
Шаг 1. Находим число
, такое, что
не является квадратом. Алгоритм для поиска таких чисел
неизвестен, за исключением метода проб и ошибок. Просто выбираем какое-либо число
и вычисляем символ Лежандра
, чтобы удостовериться, что
удовлетворяет условию. Шанс, что случайное число
подходит, равен
. Если
достаточно велико, эта величина примерно равна
[1]. Таким образом, ожидаемое число попыток для получения подходящего a равно 2.
Шаг 2. Получаем x путём вычисления
в поле
. Это число x будет одним из корней уравнения
Если
, то
также выполняется. Поскольку p нечётно,
, так что для найденного решения x всегда существует второе решение, равное -x.
(Замечание: Все элементы до второго шага принадлежат полю
, а все элементы второго шага — полю
).
Ищем число x, такое, что
Прежде чем применять алгоритм, нужно проверить, что число
является на самом деле квадратом в поле
, что означает, что символ Лежандра
должен быть равен 1. Проверить это можно с помощью критерия Эйлера:
. Это подтверждает, что 10 является квадратом и к нему можно применить алгоритм.
- Шаг 1: Находим число a, такое что
не является квадратом. Как было указано выше, нужно использовать метод проб и ошибок. Выберем число
, для него
буде равно 7. Символ Лежандра
равен -1, что можно опять получить с помощью критерия Эйлера,
. Таким образом, число
подходит.
- Шаг 2: Вычисляем
![{\displaystyle x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\right)^{7}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ed2e509d71c7b24ae89e2efe232fdf56d8d3637)
![{\displaystyle \left(2+{\sqrt {-6}}\right)^{2}=4+4{\sqrt {-6}}-6=-2+4{\sqrt {-6}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fdc048fc231e13d02cfb3a2fd346582c97f775ea)
![{\displaystyle \left(2+{\sqrt {-6}}\right)^{4}=\left(-2+4{\sqrt {-6}}\right)^{2}=-1-3{\sqrt {-6}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb6924678817b7c71d9313d58454571e73c7a23e)
![{\displaystyle \left(2+{\sqrt {-6}}\right)^{6}=\left(-2+4{\sqrt {-6}}\right)\left(-1-3{\sqrt {-6}}\right)=9+2{\sqrt {-6}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cc70bfcb87043bd68c18821927190fe6d2fb972)
![{\displaystyle \left(2+{\sqrt {-6}}\right)^{7}=\left(9+2{\sqrt {-6}}\right)\left(2+{\sqrt {-6}}\right)=6.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/659f756f1bedbada0dc2dfe5b1aa0e2116343b7a)
Таким образом,
является решением, как и
Действительно,
и
В первой части доказательства убедимся, что
действительно является полем. Для простоты выкладок введём число
, равное
. Конечно,
не является квадратичным вычетом, так что квадратный корень не существует в
. Это
, грубо говоря, можно рассматривать как аналог комплексного числа i.
Арифметика поля вполне очевидна. Сложение определяется как
.
Умножение также определяется обычным путём. Если помнить, что
, получим
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9c0ec83c9a7a6232d8a1d4b98aca8d56a7ef2dc)
.
Теперь нужно проверить свойства поля.
Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле
похоже на поле комплексных чисел (где
служит аналогом i).
Нейтральным элементом по сложению служит
или, более формально,
— если
, то
.
Нейтральным элементом по умножению служит
, точнее
:
.
Осталось проверить только, что в
существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа
является число
, которое также содержится в поле
, поскольку
. Чтобы показать, что любой ненулевой элемент
имеет обратный по умножению элемент, выпишем представления
и
. Другими словами,
.
Получаем два уравнения,
и
. Решаем эту систему относительно
и
, получим
,
.
Обратные элементы в выражениях для
и
существуют, поскольку они являются элементами поля
. Тем самым мы завершаем первую часть доказательства.
Во второй части доказательства покажем, что для любого элемента
.
По определению
не является квадратом в
. Тогда критерий Эйлера даёт
.
Таким образом,
. Это, вместе с малой теоремой Ферма (утверждающей, что
для всех
) и знанием, что в полях характеристикой выполняется равенство
, показывает желаемый результат
.
Третья и последняя часть доказательства показывает, что в случае
выполняется
.
Вычисляем
.
Заметим, что эти вычисления имеют место в
, так что
. Теорема Лагранжа утверждает, что ненулевой многочлен степени n имеет не более n корней над полем K. Если учесть, что многочлен
имеет 2 корня в
, никаких других корней быть не может
. Было показано, что
и
являются корнями многочлена
в
, так что должно выполняться
.[2]
После нахождения подходящего a число операций, требуемых алгоритмом, составляет
умножений и
сложений, где m — число знаков в двоичном представлении числа p, а k — число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Однако может посчастливиться с первого раза, но может потребоваться и более 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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34479c11f211a72ec807b93fbd791a774e01f1dc)
где
заранее известно. Это вычисление требует 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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7208d899529cf8efb669644c5b0348fa1430b477)
где
and
. Эта операция требует 6 умножений и 4 сложения.
Если предположить, что
(в случае
, прямое вычисление
много быстрее) двоичное выражение
имеет
знаков, из которых k равны единице. Таким образом, для вычисления
-ой степени числа
первую формулу нужно применить
раз, а вторую —
раз.
Алгоритм Чиполлы лучше, чем алгоритм Тонелли — Шенкса тогда и только тогда, когда
, где
максимальная степень 2, на которую делится
[3].
- E. Bach, J.O. Shallit Algorithmic Number Theory: Efficient algorithms MIT Press, (1996)