WikiSort.ru - Не сортированное

Алгори́тм Тоне́лли — Ше́нкса (названный Шенксом 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}},t\equiv n^{Q}{\pmod {p}},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}},\;t:\equiv tb^{2}{\pmod {p}},c:\equiv b^{2}{\pmod {p}}}$ and ${\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. Pp. 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. Pp. 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