Алгори́тм Тоне́лли — Ше́нкса (названный Шенксом алгоритмом RESSOL) относится к модулярной арифметике и используется для решения сравнения

${\displaystyle x^{2}\equiv n{\pmod {p)),}$

где ${\displaystyle n}$ — квадратичный вычет по модулю ${\displaystyle p}$, а ${\displaystyle p}$ — нечётное простое число.

Алгоритм Тонелли — Шенкса не может быть использован для составных модулей; поиск квадратных корней по составному модулю вычислительно эквивалентен факторизации^[1].

Эквивалентная, но немного более сложная версия этого алгоритма была разработана Альберто Тонелли в 1891 году. Версия алгоритма, обсуждаемая здесь, была разработана независимо Дэниелом Шенксом в 1973 году.

Входные данные: ${\displaystyle p}$ — нечётное простое число, ${\displaystyle n}$ — целое число, являющееся квадратичным вычетом по модулю ${\displaystyle p}$, другими словами, ${\displaystyle \left({\frac {n}{p))\right)=1}$, где ${\displaystyle \left({\frac {a}{b))\right)}$ — символ Лежандра.

Результат работы алгоритма: вычет ${\displaystyle R}$, удовлетворяющий сравнению ${\displaystyle R^{2}\equiv n{\pmod {p))}$.

1. Выделим степени двойки из ${\displaystyle p-1}$, то есть пусть ${\displaystyle p-1=2^{S}Q}$, где ${\displaystyle Q}$ нечётно, ${\displaystyle S\geqslant 1}$. Заметим, что если ${\displaystyle S=1}$, то есть ${\displaystyle p\equiv 3{\pmod {4))}$, тогда решение определяется формулой ${\displaystyle R\equiv \pm n^{\frac {p+1}{4))}$. Далее полагаем ${\displaystyle S\geqslant 2}$.
2. Выберем произвольный квадратичный невычет ${\displaystyle z}$, то есть символ Лежандра ${\displaystyle \left({\frac {z}{p))\right)=-1}$, положим ${\displaystyle c\equiv z^{Q}{\pmod {p))}$.
3. Пусть также ${\displaystyle R\equiv n^{\frac {Q+1}{2)){\pmod {p)),}$ ${\displaystyle t\equiv n^{Q}{\pmod {p)),}$ ${\displaystyle M=S.}$
4. Выполняем цикл:
   1. Если ${\displaystyle t\equiv 1{\pmod {p))}$, то алгоритм возвращает ${\displaystyle R}$.
   2. В противном случае в цикле находим наименьшее ${\displaystyle i}$, ${\displaystyle 0<i<M}$, такое, что ${\displaystyle t^{2^{i))\equiv 1{\pmod {p))}$ с помощью итерирования возведения в квадрат.
   3. Пусть ${\displaystyle b\equiv c^{2^{M-i-1)){\pmod {p))}$, и положим ${\displaystyle R:\equiv Rb{\pmod {p)),}$ ${\displaystyle t:\equiv tb^{2}{\pmod {p)),}$ ${\displaystyle c:\equiv b^{2}{\pmod {p)),}$ ${\displaystyle M:=i}$, возвращаемся к началу цикла.

После нахождения решения сравнения ${\displaystyle R}$ второе решение сравнения находится как ${\displaystyle p-R}$.

Решим сравнение ${\displaystyle x^{2}\equiv 10{\pmod {13))}$. ${\displaystyle p=13}$ — нечётно, и поскольку ${\displaystyle 10^{\frac {13-1}{2))=10^{6}\equiv 1{\pmod {13))}$, 10 является квадратичным вычетом по критерию Эйлера.

• Шаг 1: ${\displaystyle p-1=12=3\cdot 2^{2))$ поэтому ${\displaystyle Q=3}$, ${\displaystyle S=2}$.
• Шаг 2: Возьмем ${\displaystyle z=2}$ — квадратичный невычет (потому что ${\displaystyle 2^{\frac {13-1}{2))=-1{\pmod {13))}$ (снова по критерию Эйлера)). Положим ${\displaystyle c=2^{3}\equiv 8{\pmod {13)).}$
• Шаг 3: ${\displaystyle R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.}$
• Шаг 4: Начинаем цикл: ${\displaystyle t\not \equiv 1{\pmod {13))}$, так что ${\displaystyle 0<i<2}$, проще говоря ${\displaystyle i=1}$.
  • Пусть ${\displaystyle b\equiv 8^{2^{2-1-1))\equiv 8{\pmod {13))}$, тогда ${\displaystyle b^{2}\equiv 8^{2}\equiv -1{\pmod {13))}$.
  • Положим ${\displaystyle R=-4\cdot 8\equiv 7{\pmod {13))}$, ${\displaystyle t\equiv -1\cdot -1\equiv 1{\pmod {13))}$, и ${\displaystyle M=1}$.
  • Перезапустим цикл, поскольку ${\displaystyle t\equiv 1{\pmod {13))}$ цикл завершен, мы получим ${\displaystyle R\equiv 7{\pmod {13)).}$

Поскольку ${\displaystyle 7^{2}=49\equiv 10{\pmod {13))}$, очевидно ${\displaystyle (\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))}$, отсюда получаем 2 решения сравнения.

Пусть ${\displaystyle p-1=2^{S}Q}$. Пусть теперь ${\displaystyle r\equiv n^{\frac {Q+1}{2)){\pmod {p))}$ и ${\displaystyle t\equiv n^{Q}{\pmod {p))}$, заметим, что ${\displaystyle r^{2}\equiv nt{\pmod {p))}$. Последнее сравнение остается истинным после каждой итериации основного цикла алгоритма. Если в какой-то момент ${\displaystyle t\equiv 1{\pmod {p))}$, то ${\displaystyle r^{2}\equiv n{\pmod {p))}$ и алгоритм завершается с ${\displaystyle R\equiv \pm r{\pmod {p))}$.

Если ${\displaystyle t\not \equiv 1{\pmod {p))}$, то рассмотрим квадратичный невычет ${\displaystyle z}$ по модулю ${\displaystyle p}$. Пусть ${\displaystyle c\equiv z^{Q}{\pmod {p))}$, тогда ${\displaystyle c^{2^{S))\equiv (z^{Q})^{2^{S))\equiv z^{p-1}\equiv 1{\pmod {p))}$ и ${\displaystyle c^{2^{S-1))\equiv z^{\frac {p-1}{2))\equiv \left({\frac {z}{p))\right)\equiv -1{\pmod {p))}$, которое показывает, что порядок ${\displaystyle c}$ равен ${\displaystyle 2^{S))$.

Сходным образом мы получим, что ${\displaystyle t^{2^{S))\equiv 1{\pmod {p))}$, поэтому порядок ${\displaystyle t}$ делит ${\displaystyle 2^{S))$, значит порядок ${\displaystyle t}$ равен ${\displaystyle 2^{S'))$. Так как ${\displaystyle n}$ — квадрат по модулю ${\displaystyle p}$, то ${\displaystyle t\equiv n^{Q}{\pmod {p))}$ тоже квадрат, и значит, ${\displaystyle S'<S}$.

Положим, что ${\displaystyle b\equiv c^{2^{S-S'-1)){\pmod {p))}$ и ${\displaystyle r'\equiv br{\pmod {p))}$, ${\displaystyle c'\equiv b^{2}{\pmod {p))}$ и ${\displaystyle t'\equiv c't{\pmod {p))}$. Как и раньше, ${\displaystyle r'^{2}\equiv nt'{\pmod {p))}$ сохраняется; однако в этой конструкции как ${\displaystyle t}$, так и ${\displaystyle c'}$ имеют порядок ${\displaystyle 2^{S'))$. Отсюда следует, что ${\displaystyle t'}$ имеет порядок ${\displaystyle 2^{S''))$, где ${\displaystyle S''<S'}$.

Если ${\displaystyle S''=0}$, то ${\displaystyle t'\equiv 1{\pmod {p))}$, и алгоритм останавливается, возвращая ${\displaystyle R\equiv \pm r'{\pmod {p))}$. Иначе мы перезапускаем цикл с аналогичными определениями ${\displaystyle b',r'',c'',t''}$, пока не получим ${\displaystyle S^{(j)'))$, который равен 0. Поскольку последовательность натуральных ${\displaystyle S^{(j)'))$ строго убывает, то алгоритм завершается.

Алгоритм Тонелли — Шенкса выполняет в среднем (по всевозможным входам (квадратичным вычетам и невычетам))

${\displaystyle 2m+2k+{\frac {S(S-1)}{4))+{\frac {1}{2^{S-1))}-9=O(S^{2})=O(\ln ^{2}p)}$

умножений по модулю, где ${\displaystyle m=\lceil \log _{2}p\rceil =O(\ln p)}$ — число цифр в двоичном представлении ${\displaystyle p}$, и ${\displaystyle k}$ — число единиц в двоичном представлении ${\displaystyle p}$. Если требуемый квадратичный невычет ${\displaystyle z}$ будет вычисляться проверкой случайно выбранного ${\displaystyle y}$ на то, является ли оно квадратичным невычетом, то в среднем это требует вычисления двух символов Лежандра^[2]. Два как среднее число вычисляемых символов Лежандра объясняется следующим: вероятность того, что ${\displaystyle y}$ является квадратичным вычетом, равна ${\displaystyle {\frac {\frac {p+1}{2)){p))={\frac {1}{2))+{\frac {1}{2p))>{\frac {1}{2))}$ — вероятность больше половины, поэтому в среднем понадобится около двух проверок, является ли ${\displaystyle y}$ квадратичным вычетом.

Это показывает, что практически алгоритм Тонелли — Шенкса будет работать очень хорошо, если модуль ${\displaystyle p}$ случаен, то есть когда ${\displaystyle S}$ не особенно велико относительно количества цифр в двоичном представлении ${\displaystyle p}$. Алгоритм Чиполлы работает лучше, чем алгоритм Тонелли — Шенкса, если и только если ${\displaystyle S(S-1)>8m+20}$. Однако если вместо этого использовать алгоритм Сазерленда для выполнения дискретного логарифмирования в 2-Силовской подгруппе в ${\displaystyle \mathbb {F} _{p))$, это позволяет заменить ${\displaystyle S(S-1)}$ в выражении числа умножений на величину, асимптотически ограниченную ${\displaystyle O\left({\frac {S\ln S}{\ln \ln S))\right)}$^[3]. Действительно, достаточно найти одно ${\displaystyle e}$ такое, что ${\displaystyle c^{e}\equiv n^{Q))$ и тогда ${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2))$ удовлетворяет ${\displaystyle R^{2}\equiv n}$ (заметим, что ${\displaystyle e}$ кратно 2, поскольку ${\displaystyle n}$ — квадратичный вычет).

Алгоритм требует нахождения квадратичного невычета ${\displaystyle z}$. На текущий момент неизвестен детерминированный алгоритм, который бы за полиномиальное время от длины ${\displaystyle p}$ нашёл бы такое ${\displaystyle z}$. Однако, если обобщённая гипотеза Римана верна, то существует квадратичный невычет ${\displaystyle z<2\ln ^{2}{p))$,^[4], который легко найти, проверяя ${\displaystyle z}$ в указанных пределах за полиномиальное время. Это, конечно, оценка в худшем случае, поскольку, как показано было выше, достаточно проверить в среднем 2 случайных ${\displaystyle z}$ для нахождения квадратичного невычета.

Алгоритм Тонелли — Шенкса может быть использован для нахождения точек на эллиптической кривой над полем вычетов. Он также может быть использован для вычислений в криптосистеме Рабина.

Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическую группу (вместо ${\displaystyle \mathbb {F} _{p}^{\times ))$) и на нахождение корней ${\displaystyle k}$-й степени для произвольного натурального ${\displaystyle k}$, в частности, на вычисление корней ${\displaystyle k}$-й степени в конечном поле^[5].

Если надо вычислить много квадратных корней в одной и той же циклической группе и ${\displaystyle S}$ не очень велико, для улучшения и упрощения алгоритма и увеличения его скорости может быть приготовлена таблица квадратных корней квадратов элементов следующим образом:

1. Выделим степени двойки в ${\displaystyle p-1}$: пусть ${\displaystyle Q,S}$ такие, что ${\displaystyle p-1=2^{S}Q}$, ${\displaystyle Q}$ нечётно.
2. Пусть ${\displaystyle R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p))}$.
3. Найдём корень ${\displaystyle b}$ по таблице соотношений ${\displaystyle b^{2}\equiv t}$ и положим ${\displaystyle R\equiv R/b}$
4. Вернуть ${\displaystyle R}$.

• Нестеренко А. Ю. Теоретико-числовые методы в криптографии. — Москва. — 2012. — ISBN 978-5-94506-320-4.
• Ишмухаметов Ш. Т. Методы факторизации натуральных чисел. — Казанский университет. — 2011.
• Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery. An Introduction to the Theory of Numbers. — 5th. — Wiley, 1991. — ISBN 0-471-62546-9.
• 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

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина