Алгоритм Тонелли — Шенкса не может быть использован для составных модулей; поиск квадратных корней по составному модулю вычислительно эквивалентен факторизации[1].
Эквивалентная, но немного более сложная версия этого алгоритма была разработана Альберто Тонелли в 1891 году. Версия алгоритма, обсуждаемая здесь, была разработана независимо Дэниелом Шенксом в 1973 году.
Результат работы алгоритма: вычет , удовлетворяющий сравнению .
Выделим степени двойки из , то есть пусть , где нечётно, . Заметим, что если , то есть , тогда решение определяется формулой . Далее полагаем .
Выберем произвольный квадратичный невычет , то есть символ Лежандра, положим .
Пусть также
Выполняем цикл:
Если , то алгоритм возвращает .
В противном случае в цикле находим наименьшее , , такое, что с помощью итерирования возведения в квадрат.
Пусть , и положим , возвращаемся к началу цикла.
После нахождения решения сравнения второе решение сравнения находится как .
Пример
Решим сравнение . — нечётно, и поскольку , 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.
↑Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation, 80: 477—500, doi:10.1090/s0025-5718-10-02356-2
↑Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355—380, doi:10.2307/2008811, JSTOR2008811
↑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.
Литература
Нестеренко А. Ю. Теоретико-числовые методы в криптографии. — Москва. — 2012. — ISBN 978-5-94506-320-4.
Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казанский университет. — 2011.