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

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

где , так что 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].

Примечания

Литература

  • R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective. — Springer-Verlag, 2001. — ISBN 0-387-25282-7.

Ссылки

  • E. Bach, J.O. Shallit Algorithmic Number Theory: Efficient algorithms MIT Press, (1996)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.