Алгоритм Тонелли — Шенкса

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

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

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

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

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

Алгоритм

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

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

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

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

Пример

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

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

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

Доказательство

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

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

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

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

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

Скорость алгоритма

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

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

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

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

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

Применение

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

Обобщение

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

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

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