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

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

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

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

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

АлгоритмПравить

Входные данные:   — нечётное простое число,   — целое число, являющееся квадратичным вычетом по модулю  , другими словами,  , где   — символ Лежандра.

Результат работы алгоритма: вычет  , удовлетворяющий сравнению  .

  1. Выделим степени двойки из  , то есть пусть  , где   нечётно,  . Заметим, что если  , то есть  , тогда решение определяется формулой  . Далее полагаем  .
  2. Выберем произвольный квадратичный невычет  , то есть символ Лежандра  , положим  .
  3. Пусть также      
  4. Выполняем цикл:
    1. Если  , то алгоритм возвращает  .
    2. В противном случае в цикле находим наименьшее  ,  , такое, что   с помощью итерирования возведения в квадрат.
    3. Пусть  , и положим        , возвращаемся к началу цикла.

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

ПримерПравить

Решим сравнение  .   — нечётно, и поскольку  , 10 является квадратичным вычетом по критерию Эйлера.

  • Шаг 1:   поэтому  ,  .
  • Шаг 2: Возьмем   — квадратичный невычет (потому что   (снова по критерию Эйлера)). Положим  
  • Шаг 3:  
  • Шаг 4: Начинаем цикл:  , так что  , проще говоря  .
    • Пусть  , тогда  .
    • Положим  ,  , и  .
    • Перезапустим цикл, поскольку   цикл завершен, мы получим  

Поскольку  , очевидно  , отсюда получаем 2 решения сравнения.

ДоказательствоПравить

Пусть  . Пусть теперь   и  , заметим, что  . Последнее сравнение остается истинным после каждой итериации основного цикла алгоритма. Если в какой-то момент  , то   и алгоритм завершается с  .

Если  , то рассмотрим квадратичный невычет   по модулю  . Пусть  , тогда   и  , которое показывает, что порядок   равен  .

Сходным образом мы получим, что  , поэтому порядок   делит  , значит порядок   равен  . Так как   — квадрат по модулю  , то   тоже квадрат, и значит,  .

Положим, что   и  ,   и  . Как и раньше,   сохраняется; однако в этой конструкции как  , так и   имеют порядок  . Отсюда следует, что   имеет порядок  , где  .

Если  , то  , и алгоритм останавливается, возвращая  . Иначе мы перезапускаем цикл с аналогичными определениями  , пока не получим  , который равен 0. Поскольку последовательность натуральных   строго убывает, то алгоритм завершается.

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

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

 

умножений по модулю, где   — число цифр в двоичном представлении  , и   — число единиц в двоичном представлении  . Если требуемый квадратичный невычет   будет вычисляться проверкой случайно выбранного   на то, является ли оно квадратичным невычетом, то в среднем это требует вычисления двух символов Лежандра[2]. Два как среднее число вычисляемых символов Лежандра объясняется следующим: вероятность того, что   является квадратичным вычетом, равна   — вероятность больше половины, поэтому в среднем понадобится около двух проверок, является ли   квадратичным вычетом.

Это показывает, что практически алгоритм Тонелли — Шенкса будет работать очень хорошо, если модуль   случаен, то есть когда   не особенно велико относительно количества цифр в двоичном представлении  . Алгоритм Чиполлы работает лучше, чем алгоритм Тонелли — Шенкса, если и только если  . Однако если вместо этого использовать алгоритм Сазерленда для выполнения дискретного логарифмирования в 2-Силовской подгруппе в  , это позволяет заменить   в выражении числа умножений на величину, асимптотически ограниченную  [3]. Действительно, достаточно найти одно   такое, что   и тогда   удовлетворяет   (заметим, что   кратно 2, поскольку   — квадратичный вычет).

Алгоритм требует нахождения квадратичного невычета  . На текущий момент неизвестен детерминированный алгоритм, который бы за полиномиальное время от длины   нашёл бы такое  . Однако, если обобщённая гипотеза Римана верна, то существует квадратичный невычет  ,[4], который легко найти, проверяя   в указанных пределах за полиномиальное время. Это, конечно, оценка в худшем случае, поскольку, как показано было выше, достаточно проверить в среднем 2 случайных   для нахождения квадратичного невычета.

ПрименениеПравить

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

ОбобщениеПравить

Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическую группу (вместо  ) и на нахождение корней  -й степени для произвольного натурального  , в частности, на вычисление корней  -й степени в конечном поле[5].

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

  1. Выделим степени двойки в  : пусть   такие, что  ,   нечётно.
  2. Пусть  .
  3. Найдём корень   по таблице соотношений   и положим  
  4. Вернуть  .

ПримечанияПравить

  1. Oded Goldreich, Computational complexity: a conceptual perspective, Cambridge University Press, 2008, p. 588.
  2. Gonzalo Tornaria, Square roots modulo p, page 2.
  3. Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation Т. 80: 477–500, DOI 10.1090/s0025-5718-10-02356-2 
  4. Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation Т. 55 (191): 355–380, DOI 10.2307/2008811 
  5. L. M. Adleman, K. Manders, G. Miller: 1977, "On taking roots in finite fields". In: 18th IEEE Symposium on Foundations of Computer Science. p. 175–177.

ЛитератураПравить

  • Нестеренко А. Ю. Теоретико-числовые методы в криптографии. — Москва. — 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.

СсылкиПравить