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

Алгори́тм Тоне́лли — Ше́нкса (названный Шенксом алгоритмом 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