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

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

$x^2\equiv n(\mathrm{mod}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(\mathrm{mod}p)$.

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

$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-Силовской подгруппе в ${𝔽}_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$ для нахождения квадратичного невычета.

Применение

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

Обобщение

Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическую группу (вместо ${𝔽}_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}}(\mathrm{mod}p),t\equiv n^Q\equiv R^2/n(\mathrm{mod}p)$.
3. Найдём корень $b$ по таблице соотношений $b^2\equiv t$ и положим $R\equiv R/b$
4. Вернуть $R$.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• 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