Алгори́тм Тоне́лли — Ше́нкса (названный Шенксом алгоритмом RESSOL) относится к модулярной арифметике и используется для решения сравнения
где — квадратичный вычет по модулю , а — нечётное простое число.
Алгоритм Тонелли — Шенкса не может быть использован для составных модулей; поиск квадратных корней по составному модулю вычислительно эквивалентен факторизацииOded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588..
Эквивалентная, но немного более сложная версия этого алгоритма была разработана Альберто Тонелли в 1891 году. Версия алгоритма, обсуждаемая здесь, была разработана независимо Дэниелом Шенксом в 1973 году.
Алгоритм Входные данные: — нечётное простое число, — целое число, являющееся квадратичным вычетом по модулю , другими словами, , где — символ Лежандра.
Результат работы алгоритма: вычет , удовлетворяющий сравнению . Выделим степени двойки из , то есть пусть , где нечётно, . Заметим, что если , то есть , тогда решение определяется формулой . Далее полагаем . Выберем произвольный квадратичный невычет , то есть символ Лежандра , положим . Пусть также Выполняем цикл: Если , то алгоритм возвращает . В противном случае в цикле находим наименьшее , , такое, что с помощью итерирования возведения в квадрат. Пусть , и положим , возвращаемся к началу цикла.
После нахождения решения сравнения второе решение сравнения находится как .
Пример Решим сравнение . — нечётно, и поскольку , 10 является квадратичным вычетом по критерию Эйлера.
Шаг 1: поэтому , . Шаг 2: Возьмем — квадратичный невычет (потому что (снова по критерию Эйлера)). Положим Шаг 3: Шаг 4: Начинаем цикл: , так что , проще говоря . Пусть , тогда . Положим , , и . Перезапустим цикл, поскольку цикл завершен, мы получим
Поскольку , очевидно , отсюда получаем 2 решения сравнения.
Доказательство Пусть . Пусть теперь и , заметим, что . Последнее сравнение остается истинным после каждой итериации основного цикла алгоритма. Если в какой-то момент , то и алгоритм завершается с .
Если , то рассмотрим квадратичный невычет по модулю . Пусть , тогда и , которое показывает, что порядок равен .
Сходным образом мы получим, что , поэтому порядок делит , значит порядок равен . Так как — квадрат по модулю , то тоже квадрат, и значит, .
Положим, что и , и . Как и раньше, сохраняется; однако в этой конструкции как , так и имеют порядок . Отсюда следует, что имеет порядок , где .
Если , то , и алгоритм останавливается, возвращая . Иначе мы перезапускаем цикл с аналогичными определениями , пока не получим , который равен 0. Поскольку последовательность натуральных строго убывает, то алгоритм завершается.
Скорость алгоритма Алгоритм Тонелли — Шенкса выполняет в среднем (по всевозможным входам (квадратичным вычетам и невычетам))
умножений по модулю, где — число цифр в двоичном представлении , и — число единиц в двоичном представлении . Если требуемый квадратичный невычет будет вычисляться проверкой случайно выбранного на то, является ли оно квадратичным невычетом, то в среднем это требует вычисления двух символов ЛежандраGonzalo Tornaria, Square roots modulo p, page 2.. Два как среднее число вычисляемых символов Лежандра объясняется следующим: вероятность того, что является квадратичным вычетом, равна — вероятность больше половины, поэтому в среднем понадобится около двух проверок, является ли квадратичным вычетом.
Это показывает, что практически алгоритм Тонелли — Шенкса будет работать очень хорошо, если модуль случаен, то есть когда не особенно велико относительно количества цифр в двоичном представлении . Алгоритм Чиполлы работает лучше, чем алгоритм Тонелли — Шенкса, если и только если . Однако если вместо этого использовать алгоритм Сазерленда для выполнения дискретного логарифмирования в 2-Силовской подгруппе в , это позволяет заменить в выражении числа умножений на величину, асимптотически ограниченную . Действительно, достаточно найти одно такое, что и тогда удовлетворяет (заметим, что кратно 2, поскольку — квадратичный вычет).
Алгоритм требует нахождения квадратичного невычета . На текущий момент неизвестен детерминированный алгоритм, который бы за полиномиальное время от длины нашёл бы такое . Однако, если обобщённая гипотеза Римана верна, то существует квадратичный невычет ,, который легко найти, проверяя в указанных пределах за полиномиальное время. Это, конечно, оценка в худшем случае, поскольку, как показано было выше, достаточно проверить в среднем 2 случайных для нахождения квадратичного невычета.
Применение Алгоритм Тонелли — Шенкса может быть использован для нахождения точек на эллиптической кривой над полем вычетов. Он также может быть использован для вычислений в криптосистеме Рабина.
Обобщение Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическую группу (вместо ) и на нахождение корней -й степени для произвольного натурального , в частности, на вычисление корней -й степени в конечном полеL. M. Adleman, K. Manders, G. Miller: 1977, "On taking roots in finite fields". In: 18th IEEE Symposium on Foundations of Computer Science. p. 175–177..
Если надо вычислить много квадратных корней в одной и той же циклической группе и не очень велико, для улучшения и упрощения алгоритма и увеличения его скорости может быть приготовлена таблица квадратных корней квадратов элементов следующим образом: Выделим степени двойки в : пусть такие, что , нечётно. Пусть . Найдём корень по таблице соотношений и положим Вернуть .
Примечания
Литература
Daniel Shanks. Five Number Theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. P. 51–70. 1973. Alberto Tonelli, Bemerkung uber die Auflosung quadratischer Congruenzen. Nachrichten von der Koniglichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universitat zu Gottingen. P. 344—346. 1891. Gagan Tara Nanda — Mathematics 115: The RESSOL Algorithm.
Ссылки Реализация на языке Python http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
Категория:Модульная арифметика Категория:Теория чисел Категория:Криптография Категория:Теоретико-числовые алгоритмы