Алгоритм Тонелли — Шенкса не может быть использован для составных модулей; поиск квадратных корней по составному модулю вычислительно эквивалентен факторизации[1].
Эквивалентная, но немного более усложнённая версия этого алгоритма была разработана Альберто Тонелли в 1891. Версия алгоритма, обсуждаемая здесь, была разработана независимо Дэниелом Шенксом в 1973.
Входные данные: — нечётное простое число, - целое число, являющееся квадратичным вычетом по модулю , другими словами, , где — символ Лежандра.
Результат работы алгоритма: вычет , удовлетворяющий сравнению .
Выделим степени двойки из , то есть пусть , где нечётно, . Заметим, что если , то есть , тогда решение определяется формулой . Далее .
Выберем произвольный квадратичный невычет , то есть Символ Лежандра, положим .
Пусть также
Выполняем цикл:
Если , то алгоритм возвращает .
В противном случае в цикле находим наименьшее , , такое, что с помощью итерирования возведения в квадрат.
Пусть , и положим and , возвращаемся к началу цикла.
После нахождения решения сравнения второе решение сравнения находится как .
Пример
Решим сравнение . — нечётно, и поскольку , 10 является квадратичным вычетом по критерию Эйлера.
Шаг 1: поэтому , .
Шаг 2: Возьмем — квадратичный невычет (потому что (снова по критерию Эйлера)). Положим
Шаг 3:
Шаг 4: Начинаем цикл: , так что , проще говоря .
Пусть , тогда .
Положим , , и .
Перезапустим цикл, поскольку цикл завершен, мы получим
Поскольку , очевидно , отсюда получаем 2 решения сравнения.
Доказательство
Пусть . Пусть теперь и , заметим, что . Последнее сравнение остается истинным после каждой итериации основного цикла алгоритма. Если в какой-то момент , то и алгоритм завершается с .
Если , то рассмотрим квадратичный невычет по модулю . Пусть , тогда и , которое показывает, что порядок равен .
Сходным образом мы получим, что , поэтому порядок делит , значит порядок равен . Так как — квадрат по модулю , то тоже квадрат, и значит, .
Положим, что и , и . Как и раньше, сохраняется; однако в этой конструкции как , так и имеют порядок . Отсюда следует, что имеет порядок , где .
Если , то , и алгоритм останавливается, возвращая . Иначе мы перезапускаем цикл с аналогичными определениями , пока не получим , который равен 0. Поскольку последовательность натуральных строго убывает, то алгоритм завершается.
Скорость алгоритма
Алгоритм Тонелли — Шенкса выполняет в среднем (по всевозможным входам (квадратичным вычетам и невычетам))
умножений по модулю, где — число цифр в двоичном представлении и — число единиц в двоичном представлении . Если требуемый квадратичный невычет будет вычисляться проверкой случайно выбранного на то, является ли оно квадратичным невычетом, то в среднем это требует вычисления двух символов Лежандра[2]. Два как среднее число вычисляемых символов Лежандра объясняется следующим: вероятность того, что является квадратичным вычетом, равна — вероятность больше половины, поэтому в среднем понадобится около двух проверок, является ли квадратичным вычетом.
Это показывает, что практически алгоритм Тонелли — Шенкса будет работать очень хорошо, если модуль случаен, то есть когда не особенно велико относительно количества цифр в двоичном представлении . Алгоритм Чиполлы работает лучше, чем алгоритм Тонелли — Шенкса, если и только если . Однако если вместо этого использовать алгоритм Сазерленда для выполнения дискретного логарифмирования в 2-Силовской подгруппе в , это позволяет заменить в выражении числа умножений на величину, асимптотически ограниченную [3]. Действительно, достаточно найти одно такое, что и тогда удовлетворяет (заметим, что кратно 2, поскольку — квадратичный вычет).
Алгоритм требует нахождения квадратичного невычета . На текущий момент неизвестен детерминированный алгоритм, который бы за полиномиальное время от длины нашел бы такое . Однако, если обобщенная гипотеза Римана верна, то существует квадратичный невычет ,[4], который легко найти проверяя в указанных пределах за полиномиальное время. Это, конечно, оценка в худшем случае, поскольку, как показано было выше, достаточно проверить в среднем 2 случайных для нахождения квадратичного невычета.
Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическую группу (вместо ) и на нахождение корней -й степени для произвольного натурального , в частности, на вычисление корней -й степени в конечном поле[5].
Если надо вычислить много квадратных корней в одной и той же циклической группе и не очень велико, для улучшения и упрощения алгоритма и увеличения его скорости может быть приготовлена таблица квадратных корней квадратов элементов следующим образом:
Выделим степени двойки в : пусть такие, что , нечётно.
Пусть .
Найдём корень по таблице соотношений и положим
Вернуть .
Примечания
↑Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.
Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation Т. 80: 477–500, DOI 10.1090/s0025-5718-10-02356-2
Explicit bounds for primality testing and related problems", Mathematics of Computation Т. 55 (191): 355–380, DOI 10.2307/2008811
↑Adleman, L. M., K. Manders, and G. Miller: 1977, `On taking roots in finite fields'. In: 18th IEEE Symposium on Foundations of Computer Science. pp.175-177
Литература
Нестеренко А.Ю. Теоретико-числовые методы в криптографии. — Москва. — 2012. — ISBN 978-5-94506-320-4.
Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. — Казанский университет. — 2011.
Daniel Shanks. Five Number Theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 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. Pp. 344—346. 1891. [1]
Gagan Tara Nanda — Mathematics 115: The RESSOL Algorithm [2]
Ссылки
Implementation in Python http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python