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

где
, так что n будет квадратом числа x, и где
является нечётным простым числом. Здесь
обозначает конечное поле с
элементами
. Алгоритм носит имя итальянского математика Микеле Чиполлы[англ.], открывшего метод в 1907.
Алгоритм
Вход:
, нечётное простое число,
, квадрат числа.
Выход:
- число
, удовлетворяющее равенству 
Шаг 1. Находим число
, такое, что
не является квадратом. Алгоритм для поиска таких чисел
неизвестен, за исключением метода проб и ошибок. Просто выбираем какое-либо число
и вычисляем символ Лежандра
, чтобы удостовериться, что
удовлетворяет условию. Шанс, что случайное число
подходит, равен
. Если
достаточно велико, эта величина примерно равна
[1]. Таким образом, ожидаемое число попыток для получения подходящего a равно 2.
Шаг 2. Получаем x путём вычисления
в поле
. Это число x будет одним из корней уравнения 
Если
, то
также выполняется. Поскольку p нечётно,
, так что для найденного решения x всегда существует второе решение, равное -x.
Пример
(Замечание: Все элементы до второго шага принадлежат полю
, а все элементы второго шага — полю
). Ищем число x, такое, что 
Прежде чем применять алгоритм, нужно проверить, что число
является на самом деле квадратом в поле
, что означает, что символ Лежандра
должен быть равен 1. Проверить это можно с помощью критерия Эйлера:
. Это подтверждает, что 10 является квадратом и к нему можно применить алгоритм.
- Шаг 1: Находим число a, такое что
не является квадратом. Как было указано выше, нужно использовать метод проб и ошибок. Выберем число
, для него
буде равно 7. Символ Лежандра
равен -1, что можно опять получить с помощью критерия Эйлера,
. Таким образом, число
подходит. - Шаг 2: Вычисляем





Таким образом,
является решением, как и
Действительно,
и 
Доказательство
В первой части доказательства убедимся, что
действительно является полем. Для простоты выкладок введём число
, равное
. Конечно,
не является квадратичным вычетом, так что квадратный корень не существует в
. Это
, грубо говоря, можно рассматривать как аналог комплексного числа i. Арифметика поля вполне очевидна. Сложение определяется как
.
Умножение также определяется обычным путём. Если помнить, что
, получим

.
Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность, коммутативность и дистрибутивность легко проверить, поскольку поле
похоже на поле комплексных чисел (где
служит аналогом i).
Нейтральным элементом по сложению служит
или, более формально,
— если
, то
.
Нейтральным элементом по умножению служит
, точнее
:
.
Осталось проверить только, что в
существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа
является число
, которое также содержится в поле
, поскольку
. Чтобы показать, что любой ненулевой элемент
имеет обратный по умножению элемент, выпишем представления
и
. Другими словами,
.
Получаем два уравнения,
и
. Решаем эту систему относительно
и
, получим
,
.
Обратные элементы в выражениях для
и
существуют, поскольку они являются элементами поля
. Тем самым мы завершаем первую часть доказательства.
Во второй части доказательства покажем, что для любого элемента
. По определению
не является квадратом в
. Тогда критерий Эйлера даёт
.
Таким образом,
. Это, вместе с малой теоремой Ферма (утверждающей, что
для всех
) и знанием, что в полях характеристикой выполняется равенство
, показывает желаемый результат
.
Третья и последняя часть доказательства показывает, что в случае
выполняется
.
Вычисляем
.
Заметим, что эти вычисления имеют место в
, так что
. Теорема Лагранжа утверждает, что ненулевой многочлен степени n имеет не более n корней над полем K. Если учесть, что многочлен
имеет 2 корня в
, никаких других корней быть не может
. Было показано, что
и
являются корнями многочлена
в
, так что должно выполняться
.[2]
Скорость
После нахождения подходящего a число операций, требуемых алгоритмом, составляет
умножений и
сложений, где m — число знаков в двоичном представлении числа p, а k — число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Однако может посчастливиться с первого раза, но может потребоваться и более 2 попыток. В поле
выполняются следующие два равенства

где
заранее известно. Это вычисление требует 4 умножения и 4 сложения.

где
and
. Эта операция требует 6 умножений и 4 сложения.
Если предположить, что
(в случае
, прямое вычисление
много быстрее) двоичное выражение
имеет
знаков, из которых k равны единице. Таким образом, для вычисления
-ой степени числа
первую формулу нужно применить
раз, а вторую —
раз.
Алгоритм Чиполлы лучше, чем алгоритм Тонелли — Шенкса тогда и только тогда, когда
, где
максимальная степень 2, на которую делится
[3].
Примечания
Литература
Ссылки
- E. Bach, J.O. Shallit Algorithmic Number Theory: Efficient algorithms MIT Press, (1996)