Алгоритм Чиполласа - Википедия - Cipollas algorithm

В вычислительная теория чисел, Алгоритм Чиполлы это метод решения соответствие формы

куда , так п это квадрат Икс, и где является странный основной. Здесь обозначает конечный поле с элементы; . В алгоритм назван в честь Мишель Чиполла, Итальянский математик открывший его в 1907 году.

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

Алгоритм

Входы:

  • , нечетное простое число,
  • , который представляет собой квадрат.

Выходы:

  • , удовлетворяющий

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

Шаг 2 - вычислить Икс вычисляя в поле . Этот Икс будет единственным удовлетворением

Если , тогда также имеет место. И с тех пор п странно, . Поэтому всякий раз, когда решение Икс найден, всегда есть второе решение, -Икс.

Пример

(Примечание: все элементы до шага два рассматриваются как элемент и все элементы на втором шаге рассматриваются как элементы ).

Найти все Икс такой, что

Перед применением алгоритма необходимо проверить, что действительно квадрат в . Следовательно, символ Лежандра должно быть равно 1. Это можно вычислить, используя Критерий Эйлера; Это подтверждает, что 10 является квадратом, и, следовательно, алгоритм может быть применен.

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

Так это решение, а также В самом деле, и

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

Первая часть доказательства - проверить, что действительно поле. Для простоты обозначений определяется как . Конечно, является квадратичным невычетом, поэтому нет квадратный корень в . Этот можно примерно рассматривать как аналог комплексного числа я.Полевая арифметика вполне очевидна. Добавление определяется как

.

Умножение также определяется как обычно. Имея в виду, что , это становится

.

Теперь нужно проверить свойства поля: свойства замыкания при сложении и умножении, ассоциативность, коммутативность и распределенность легко увидеть. Это потому, что в этом случае поле чем-то напоминает поле сложные числа являясь аналогом я).
Добавка личность является , или более формально : Позволять , тогда

.

Мультипликативное тождество , или более формально :

.

Единственное, что осталось для Быть полем - это наличие аддитивного и мультипликативного обратное. Легко видеть, что аддитивная инверсия является , который является элементом , потому что . Фактически, это аддитивные обратные элементы Икс и у. Чтобы показать, что каждый ненулевой элемент имеет мультипликативный обратный, запишите и . Другими словами,

.

Итак, два равенства и должен держать. Проработка деталей дает выражения для и , а именно

,
.

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

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

.

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

.

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

.

Обратите внимание, что это вычисление происходило в так что это . Но с Теорема Лагранжа, утверждая, что ненулевое многочлен степени п имеет самое большее п корни в любой сфере K, и знание, что имеет 2 корня в , эти корни должны быть всеми корнями в . Только что было показано, что и корни в , так должно быть, что .[3]

Скорость

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

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

куда и . Для этой операции требуется 6 умножений и 4 суммы.

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

Для этого алгоритм Чиполлы лучше, чем Алгоритм Тонелли – Шанкса если и только если , с максимальная степень двойки, которая делит .[4]

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

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

куда и
куда , как в примере из этой статьи

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


В качестве

Теперь решите для через:

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

В качестве таких:

и

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

что и есть ответ.

Рекомендации

  1. ^ "История теории чисел" Том 1 Леонарда Юджина Диксона, стр. 218читать онлайн
  2. ^ Р. Крэндалл, Простые числа К. Померанса: вычислительная перспектива Springer-Verlag, (2001) с. 157
  3. ^ М. Бейкер Алгоритм Чиполлы нахождения квадратных корней по модулю p
  4. ^ Гонсало Торнария Квадратные корни по модулю p
  5. ^ "История теории чисел" Том 1 Леонарда Юджина Диксона, стр. 218, Chelsea Publishing, 1952 г.читать онлайн
  6. ^ Мишель Чиполла, Rendiconto dell 'Accademia delle Scienze Fisiche e Matematiche. Неаполь, (3), 10,1904, 144-150

Источники

  • Э. Бах, Дж. Шаллит Алгоритмическая теория чисел: эффективные алгоритмы MIT Press, (1996)
  • Леонард Юджин Диксон История теории чисел Том 1, с. 218 [1]
  1. ^ "История теории чисел" Том 1 Леонарда Юджина Диксона, стр. 218, Chelsea Publishing, 1952 г.url =https://archive.org/details/historyoftheoryo01dick