В вычислительная теория чисел, Алгоритм Чиполлы это метод решения соответствие формы
куда , так п это квадрат Икс, и где является странный основной. Здесь обозначает конечный поле с элементы; . В алгоритм назван в честь Мишель Чиполла, Итальянский математик открывший его в 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 Леонарда Юджина Диксона, стр. 218читать онлайн
- ^ Р. Крэндалл, Простые числа К. Померанса: вычислительная перспектива Springer-Verlag, (2001) с. 157
- ^ М. Бейкер Алгоритм Чиполлы нахождения квадратных корней по модулю p
- ^ Гонсало Торнария Квадратные корни по модулю p
- ^ "История теории чисел" Том 1 Леонарда Юджина Диксона, стр. 218, Chelsea Publishing, 1952 г.читать онлайн
- ^ Мишель Чиполла, Rendiconto dell 'Accademia delle Scienze Fisiche e Matematiche. Неаполь, (3), 10,1904, 144-150
Источники
- Э. Бах, Дж. Шаллит Алгоритмическая теория чисел: эффективные алгоритмы MIT Press, (1996)
- Леонард Юджин Диксон История теории чисел Том 1, с. 218 [1]