Русская Википедия:Алгоритм Тонелли — Шенкса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

<math> x^2 \equiv n \pmod p, </math>

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

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

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

Алгоритм

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

Обобщение

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

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

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

Литература

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