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

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

x2n(modp),
 где n — квадратичный вычет по модулю p, а p — нечётное простоечисло.
 Алгоритм Тонелли — Шенкса не может быть использован для составныхмодулей; поиск квадратных корней по составному модулю вычислительноэквивалентен факторизации.
 Эквивалентная, но немного более усложнённая версия этого алгоритма быларазработана Альберто Тонелли в 1891 году. Версия алгоритма, обсуждаемаяздесь, была разработана независимо Дэниелом Шенксом в 1973 году.

Алгоритм


Входные данные: p — нечётное простое число, n - целоечисло, являющееся квадратичным вычетом по модулю p, другими словами,(np)=1, где (ab) — символЛежандра.
Результат работы алгоритма: вычет R, удовлетворяющийсравнению R2n(modp).

  1. Выделим степени двойки из p1, то есть пусть p1=2SQ, где Q нечётно, S1. Заметим, что если S=1, то есть p3(mod4), тогда решение определяется формулой R±np+14. Далее S2.
  2. Выберем произвольный квадратичный невычет z, то есть символ Лежандра (zp)=1, положим czQ(modp).
  3. Пусть также RnQ+12(modp),tnQ(modp),M=S.
  4. Выполняем цикл:
    1. Если t1(modp), то алгоритм возвращает R.
    2. В противном случае в цикле находим наименьшее i, 0<i<M, такое, что t2i1(modp) с помощью итерирования возведения в квадрат.
    3. Пусть bc2(Mi1)(modp), и положим R:≡Rb(modp),t:≡tb2(modp),c:≡b2(modp) and M:=i, возвращаемся к началу цикла.

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

Пример


 Решим сравнение x210(mod13). p=13 — нечётно, ипоскольку 101312=1061(mod13), 10 являетсяквадратичным вычетом по критерию Эйлера.

  • Шаг 1: p1=12=322 поэтому Q=3, S=2.
  • Шаг 2: Возьмем z=2 — квадратичный невычет (потому что 21312=1(mod13) (снова по критерию Эйлера)). Положим c=238(mod13).
  • Шаг 3: R=1024,t1031(mod13),M=2.
  • Шаг 4: Начинаем цикл: t1(mod13), так что 0<i<2, проще говоря i=1.
    • Пусть b822118(mod13), тогда b2821(mod13).
    • Положим R=487(mod13), t111(mod13), и M=1.
    • Перезапустим цикл, поскольку t1(mod13) цикл завершен, мы получим R7(mod13).

 Поскольку 72=4910(mod13), очевидно(±7)26210(mod13), отсюда получаем 2 решениясравнения.

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


 Пусть p1=2SQ. Пусть теперь rnQ+12(modp) иtnQ(modp), заметим, что r2nt(modp). Последнеесравнение остается истинным после каждой итериации основного циклаалгоритма. Если в какой-то момент t1(modp), тоr2n(modp) и алгоритм завершается сR±r(modp).
 Если t1(modp), то рассмотрим квадратичный невычет z помодулю p. Пусть czQ(modp), тогдаc2S(zQ)2Szp11(modp) иc2S1zp12(zp)1(modp),которое показывает, что порядок c равен 2S.
 Сходным образом мы получим, что t2S1(modp), поэтомупорядок t делит 2S, значит порядок t равен 2S. Так какn — квадрат по модулю p, то tnQ(modp) тоже квадрат, изначит, $S' Положим, что bc2SS1(modp) и rbr(modp),cb2(modp) и tct(modp). Как и раньше,r2nt(modp) сохраняется; однако в этой конструкции какt, так и c имеют порядок 2S. Отсюда следует, что t имеетпорядок 2S, где S<S.
 Если S=0, то t1(modp), и алгоритм останавливается,возвращая R±r(modp). Иначе мы перезапускаем цикл саналогичными определениями b,r,c,t, пока не получимS(j), который равен 0. Поскольку последовательность натуральныхS(j) строго убывает, то алгоритм завершается.

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


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

2m+2k+S(S1)4+12S19=O(S2)=O(ln2p)
 умножений по модулю, где m=log2p=O(lnp) — числоцифр в двоичном представлении p и k — число единиц в двоичномпредставлении p. Если требуемый квадратичный невычет z будетвычисляться проверкой случайно выбранного y на то, является ли оноквадратичным невычетом, то в среднем это требует вычисления двухсимволов Лежандра. Два как среднее число вычисляемых символов Лежандраобъясняется следующим: вероятность того, что y является квадратичнымвычетом, равнаp+12p=12+12p>12 —вероятность больше половины, поэтому в среднем понадобится около двухпроверок, является ли y квадратичным вычетом.
 Это показывает, что практически алгоритм Тонелли — Шенкса будетработать очень хорошо, если модуль p случаен, то есть когда S неособенно велико относительно количества цифр в двоичном представленииp. Алгоритм Чиполлы работает лучше, чем алгоритм Тонелли — Шенкса,если и только если S(S1)>8m+20. Однако если вместо этогоиспользовать алгоритм Сазерленда для выполнения дискретногологарифмирования в 2-Силовской подгруппе в Fp, это позволяетзаменить S(S1) в выражении числа умножений на величину,асимптотически ограниченную O(SlnSlnlnS).Действительно, достаточно найти одно e такое, что cenQ итогда Rce/2n(Q+1)/2 удовлетворяет R2n(заметим, что e кратно 2, поскольку n — квадратичный вычет).
 Алгоритм требует нахождения квадратичного невычета z. На текущиймомент неизвестен детерминированный алгоритм, который бы заполиномиальное время от длины p нашел бы такое z. Однако, еслиобобщенная гипотеза Римана верна, то существует квадратичный невычетz<2ln2p,, который легко найти проверяя z в указанных пределахза полиномиальное время. Это, конечно, оценка в худшем случае,поскольку, как показано было выше, достаточно проверить в среднем 2случайных z для нахождения квадратичного невычета.

Применение


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

Обобщение


 Алгоритм Тонелли — Шенкса может быть обобщён на любую циклическуюгруппу (вместо Fp×) и на нахождение корней k-йстепени для произвольного натурального k, в частности, на вычислениекорней k-й степени в конечном поле.
 Если надо вычислить много квадратных корней в одной и той же циклическойгруппе и S не очень велико, для улучшения и упрощения алгоритма иувеличения его скорости может быть приготовлена таблица квадратныхкорней квадратов элементов следующим образом:

  1. Выделим степени двойки в p1: пусть Q,S такие, что p1=2SQ, Q нечётно.
  2. Пусть RnQ+12(modp),tnQR2/n(modp).
  3. Найдём корень b по таблице соотношений b2t и положим RR/b
  4. Вернуть R.