Interested Article - Алгоритм Чиполлы

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

где , так что n будет квадратом числа x , и где является нечётным простым числом. Здесь обозначает конечное поле с элементами . Алгоритм носит имя итальянского математика , открывшего метод в 1907.

Алгоритм

Вход:

  • , нечётное простое число,
  • , квадрат числа.

Выход:

  • число , удовлетворяющее равенству

Шаг 1. Находим число , такое, что не является квадратом. Алгоритм для поиска таких чисел неизвестен, за исключением метода проб и ошибок . Просто выбираем какое-либо число и вычисляем символ Лежандра , чтобы удостовериться, что удовлетворяет условию. Шанс, что случайное число подходит, равен . Если достаточно велико, эта величина примерно равна . Таким образом, ожидаемое число попыток для получения подходящего a равно 2.

Шаг 2. Получаем x путём вычисления в поле . Это число x будет одним из корней уравнения

Если , то также выполняется. Поскольку p нечётно, , так что для найденного решения x всегда существует второе решение, равное -x .

Пример

( Замечание : Все элементы до второго шага принадлежат полю , а все элементы второго шага — полю ). Ищем число x , такое, что

Прежде чем применять алгоритм, нужно проверить, что число является на самом деле квадратом в поле , что означает, что символ Лежандра должен быть равен 1. Проверить это можно с помощью критерия Эйлера : . Это подтверждает, что 10 является квадратом и к нему можно применить алгоритм.

  • Шаг 1: Находим число a , такое что не является квадратом. Как было указано выше, нужно использовать метод проб и ошибок. Выберем число , для него буде равно 7. Символ Лежандра равен -1, что можно опять получить с помощью критерия Эйлера, . Таким образом, число подходит.
  • Шаг 2: Вычисляем

Таким образом, является решением, как и Действительно, и

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

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

.

Умножение также определяется обычным путём. Если помнить, что , получим

.

Теперь нужно проверить свойства поля. Замкнутость по операциям сложения и умножения, ассоциативность , коммутативность и дистрибутивность легко проверить, поскольку поле похоже на поле комплексных чисел (где служит аналогом i ).
Нейтральным элементом по сложению служит или, более формально, — если , то

.

Нейтральным элементом по умножению служит , точнее :

.

Осталось проверить только, что в существуют обратные элементы по сложению и умножению. Легко видеть, что обратным элементом по сложению числа является число , которое также содержится в поле , поскольку . Чтобы показать, что любой ненулевой элемент имеет обратный по умножению элемент, выпишем представления и . Другими словами,

.

Получаем два уравнения, и . Решаем эту систему относительно и , получим

,
.

Обратные элементы в выражениях для и существуют, поскольку они являются элементами поля . Тем самым мы завершаем первую часть доказательства.

Во второй части доказательства покажем, что для любого элемента . По определению не является квадратом в . Тогда критерий Эйлера даёт

.

Таким образом, . Это, вместе с малой теоремой Ферма (утверждающей, что для всех ) и знанием, что в полях характеристикой выполняется равенство , показывает желаемый результат

.

Третья и последняя часть доказательства показывает, что в случае выполняется .
Вычисляем

.

Заметим, что эти вычисления имеют место в , так что . Теорема Лагранжа утверждает, что ненулевой многочлен степени n имеет не более n корней над полем K . Если учесть, что многочлен имеет 2 корня в , никаких других корней быть не может . Было показано, что и являются корнями многочлена в , так что должно выполняться .

Скорость

После нахождения подходящего a число операций, требуемых алгоритмом, составляет умножений и сложений, где m — число знаков в двоичном представлении числа p , а k — число единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое число вычислений символа Лежандра равно 2. Однако может посчастливиться с первого раза, но может потребоваться и более 2 попыток. В поле выполняются следующие два равенства

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

где and . Эта операция требует 6 умножений и 4 сложения.

Если предположить, что (в случае , прямое вычисление много быстрее) двоичное выражение имеет знаков, из которых k равны единице. Таким образом, для вычисления -ой степени числа первую формулу нужно применить раз, а вторую — раз.

Алгоритм Чиполлы лучше, чем алгоритм Тонелли — Шенкса тогда и только тогда, когда , где максимальная степень 2, на которую делится .

Примечания

  1. , с. 157.
  2. . Дата обращения: 29 июня 2017. 25 марта 2017 года.
  3. (недоступная ссылка)

Литература

Ссылки

  • E. Bach, J.O. Shallit Algorithmic Number Theory: Efficient algorithms MIT Press, (1996)


Источник —

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