В теории вычислений чисел , алгоритм Cipolla в это метод решения конгруэнтности вида
где , поэтому n - квадрат x , а гдеявляется нечетным простым . Здесьобозначает конечное поле с элементы ;. Алгоритм назван в честь Мишель Cipolla , с итальянским математиком , который открыл его в 1907 году.
Помимо модулей простых чисел, алгоритм Чиполлы также может извлекать квадратные корни по модулю простых степеней. [1]
Входы:
- , нечетное простое число,
- , который представляет собой квадрат.
Выходы:
- , удовлетворяющий
Шаг 1 - найти такой, что это не квадрат. Нет известного алгоритма поиска такого, кроме метода проб и ошибок . Просто выберитеи вычисляя символ Лежандра можно увидеть, есть ли удовлетворяет условию. Вероятность того, что случайный удовлетворит . С участием достаточно большой, это примерно . [2] Таким образом, ожидаемое количество испытаний перед поиском подходящего около 2.
Шаг 2 - вычислить x путем вычисления в поле . Этот x будет единственным удовлетворительным
Если , тогда также имеет место. А поскольку p нечетное,. Таким образом, всякий раз, когда найдено решение x , всегда есть второе решение, -x .
(Примечание: все элементы до шага два рассматриваются как элемент и все элементы на втором шаге рассматриваются как элементы ).
Найдите все x такие, что
Перед применением алгоритма необходимо проверить, что действительно квадрат в . Следовательно, символ Лежандрадолжно быть равно 1. Это можно вычислить с использованием критерия Эйлера ; Это подтверждает, что 10 является квадратом, и, следовательно, алгоритм может быть применен.
- Шаг 1: Найти лучше таким образом, чтоэто не квадрат. Как уже говорилось, это нужно делать методом проб и ошибок. Выбирать. потом становится 7. Символ Лежандра должно быть -1. Опять же, это можно вычислить с помощью критерия Эйлера. Так является подходящим выбором для .
- Шаг 2: вычислить
Так это решение, а также Действительно, а также
Первая часть доказательства состоит в том, чтобы проверить, что действительно поле. Для простоты обозначений определяется как . Конечно,не квадратичный невычет, так что нет квадратного корня в. Этотможно примерно рассматривать как аналог комплексного числа i . Полевая арифметика вполне очевидна. Дополнение определяется как
- .
Умножение также определяется как обычно. Имея в виду, что, это становится
- .
Теперь нужно проверить свойства поля. Свойства замыкания относительно сложения и умножения, ассоциативности , коммутативности и дистрибутивности легко увидеть. Это потому, что в этом случае полечем-то напоминает поле комплексных чисел (сявляясь аналогом i ).
Добавка идентичность является, или более формально : Позволять , тогда
- .
Мультипликативное тождество , или более формально :
- .
Единственное, что осталось для Быть полем означает существование аддитивных и мультипликативных инверсий . Легко видеть, что аддитивная инверсия является , который является элементом , так как . Фактически, это аддитивные элементы, обратные x и y . Чтобы показать, что каждый ненулевой элемент имеет мультипликативный обратный, запишите а также . Другими словами,
- .
Итак, два равенства а также должен держать. Проработка деталей дает выражения для а также , а именно
- ,
- .
Обратные элементы, которые показаны в выражениях а также существуют, потому что это все элементы . Это завершает первую часть доказательства, показывая, что это поле.
Вторая и средняя часть доказательства показывает, что для каждого элемента . По определению, это не квадрат в . Тогда критерий Эйлера говорит, что
- .
Таким образом . Это вместе с маленькой теоремой Ферма (которая гласит, что для всех ) и знание того, что в полях характеристики p уравнениеотношения, иногда называемые мечтой первокурсника , показывают желаемый результат
- .
Третья и последняя часть доказательства состоит в том, чтобы показать, что если , тогда .
Вычислить
- .
Обратите внимание, что это вычисление проводилось в так что это . Но с теоремой Лагранжа , утверждающей, что ненулевой многочлен степени n имеет не более n корней в любом поле K , и знанием, что имеет 2 корня в , эти корни должны быть всеми корнями в . Только что было показано, что а также корни в , так должно быть, что . [3]
После нахождения подходящего a количество операций, необходимых для алгоритма, равно умножения суммы, где т представляет собой количество цифр в двоичном представлении о р и к этому числу единиц в этом представлении. Чтобы найти a методом проб и ошибок, ожидаемое количество вычислений символа Лежандра равно 2. Но может повезти с первой попытки, и может потребоваться более двух попыток. В поле, выполняются следующие два равенства
где известно заранее. Это вычисление требует 4 умножения и 4 сумм.
где а также . Эта операция требует 6 умножений и 4 сумм.
При условии, что (в случае , прямое вычисление намного быстрее) двоичное выражение имеет цифры, из которых k - единицы. Итак, для вычисления сила , необходимо использовать первую формулу раз и второй раз.
Для этого алгоритм Чиполлы лучше алгоритма Тонелли – Шанкса тогда и только тогда, когда, с участием максимальная степень двойки, которая делит . [4]